백준 13164 행복 유치원 문제 풀이
백준 13164 행복 유치원 문제 풀이
백준 온라인 저지, 13164번: 행복 유치원
도입
백준 온라인 저지 2212번: 센서 문제와 같은 방법으로 풀 수 있는 문제이다. 실제로 입력 형식만 조금 조정하면 같은 코드로 통과한다.
주어진 값을 일정한 수의 집합으로 나누어 그 집합 내에서의 최대값과 최소값의 차이, 즉 최대 차이를 최소화해야 한다.
다시 말해, 주어진 값을 수직선 상에서 표현했을 때 각 집합이 수직선 상에서 가장 잘 뭉쳐있도록 해야 한다. 한데 잘 뭉쳐있다는 것은 집합 내의 값은 주어진 수를 정렬하였을 때, 연속된 구간에 속한다는 것을 시사한다.
연속된 구간을 집합으로 설정하는 편이 그렇지 않은 상황에 비해서 집합의 최대 차이를 더 줄일 수 있다.
문제 풀이
1
2
coords.sort()
dist = [coords[i] - coords[i - 1] for i in range(1, N)]
주어진 수를 정렬하여 모든 인접한 두 수의 차이를 구한다. 이렇게 구한 차이는 가능한 모든 두 수의 차이 중에서 가장 작은 부분 집합이다. 어떤 방식으로 두 수를 선택하여 차이를 구하든 인접한 두 수가 아니라면, 차이는 인접한 두 수의 차이보다 작을 수는 없다.
1
2
3
4
dist.sort()
for i in range(K - 1):
dist.pop()
각 집합의 최대 차이를 최소화하려면, 각 집합에서 가장 큰 차이를 발생시킬 수 있는 인접한 두 수를 서로 다른 집합으로 분리하는 것이 좋다. 최대 차이를 이루는 두 수의 구간은 모든 인접한 두 수의 구간을 내포하므로, 이와 같이 집합을 분리하여 집합 안에서 인접한 두 수의 차이를 줄인다.