2141번: 우체국
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.
www.acmicpc.net
해당 문제는 1시간 정도 고민하고 코드를 짜면서 도전했는데 이중for문을 써서 계속 시간 초과가 떴다. 이후에 이중for문을 사용하지 않는 다른 방법도 시도해 보았지만 점점 산으로 가는 것 같아서 결국 다른 분 코드를 참고했다.
풀이를 보자마자 아! 했다. 그리디 문제는 아이디어를 떠올리는 것이 가장 어려운 것 같다.
그리디로 풀 때는 구하고자 하는 것에 집중하면서 푸는 연습을 해야할 것 같다.
해당 문제를 예시로 들면, 각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다라는 문장이 매우 중요한 조건이 된다. 여기서 거리에 현혹되지 말고 '사람'에 포커스를 맞추고 사람 수를 중심으로 풀어나가야 한다.
for(int i=0; i < N; i++){
result += li.get(i).people;
if((sum + 1)/2 <= result){
bw.write(String.valueOf(li.get(i).vil));
break;
}
}
중간값을 구하고 처음부터 마을을 순회하다가 사람 수가 처음으로 중간 값 이상이 되는 지점에 우체국을 지으면 된다.
'Algorithms > study log' 카테고리의 다른 글
[투포인터] 백준 20922 겹치는 건 싫어 (1) | 2024.04.09 |
---|---|
[백트래킹] 눈덩이 굴리기, 근손실, 1,2,3 더하기 2 (1) | 2024.04.07 |
[Greedy] 연속되는 조건이 있는 문제 (1) | 2024.03.17 |
[java] 트리와 DFS (0) | 2024.02.26 |
[java] 큐 / 우선순위 큐 / 힙 (0) | 2024.02.23 |