[#25][알고리즘] 공항 건설하기
프로그래머스 > 공항 건설하기
문제 링크(https://programmers.co.kr/learn/challenge_codes/183)
C++풀이
#include<algorithm>
#include<iostream>
#include<vector>
#include<utility>
using namespace std;
int chooseCity(int n, vector<pair<int,int>> city)
{
// 도시 좌표 순서로 정렬
sort(city.begin(), city.end());
int answer;
long long sum = 0;
long long num = 0;
// 인구 수 총 합 구하기
for(int i = 0; i < n; i++)
sum += city[i].second;
// 인구 수의 50%가 넘는 시점의 인덱스 j를 answer에 저장
for(int j = 0; j < n ; j++){
num += city[j].second;
if(num >= sum/2){
answer = j;
break;
}
}
// answer에 있는 도시 위치 return
return city[answer].first;
}
int main()
{
int tn = 3;
pair<int,int> a,b,c;
a.first = 1, a.second = 5;
b.first = 2, b.second = 2;
c.first = 3, c.second = 3;
vector<pair<int,int>> tcity{a,b,c};
//아래는 테스트 출력을 위한 코드입니다.
cout<<chooseCity(tn,tcity);
}
| cs |
원래는 공항 위치에 따른 사람들의 이동거리를 하나하나 계산하는 방식으로 코딩
테스트 케이스의 수가 적은 경우 올바른 답이 나오지만
프로그래머스 제출시 테스트 케이스의 수가 너무 커서 그런지 정답이 아닌 것으로 나옴
왜 안되는지 모르겠음 ㅠㅠㅠㅠㅠㅠ엉엉,,,
for(int i = 0; i < n; i++){
distance = 0;
for(int j = 0; j < n; j++){
if(i!=j){
distance += abs(city[j].first - city[i].first) * city[j].second;
}
}
//cout << "distance : " << distance << endl;
if( answer > distance ){
answer = distance;
index = i;
//cout << "최소값을 가진 인덱스 : " << index << endl;
}
}
| cs |
댓글
댓글 쓰기