문제 정보
- https://www.acmicpc.net/problem/2203
- 무작위화, 정렬
- DP, 정렬
문제 정리
도시가 3N개 있고, 각 도시의 인구는 1,000명이다. 각 도시의 월드당 지지자 수가 주어질 때, 도시를 N개씩 세 선거구로 나눈다.
어떤 선거구에서 월드당 지지자 합이 500N을 초과하면 그 선거구는 월드당을 지지하는 것으로 보며, 월드당이 당선되려면 세 선거구 중 최소 2개의 선거구가 월드당을 지지해야 한다.
항상 정답이 존재하는 케이스만 주어질 때, 도시를 어떻게 배치해야 하는지 구해보는 문제이다.
풀이
2N개의 도시를 선거구A, B에 배정한 경우 나머지 N개는 선거구C에 배정된다. 여기까지는 생각했는데, 그 뒤는 아무리 생각해도 모르겠어서 인터넷의 도움을 받았다. 이 문제에서 필요한 관찰은 다음과 같다.
- 하위 N개를 선거구C에 고정.
- 3개 중 2개의 선거구에서만 이기면 되므로, 지지자 수 하위 N개는 한 선거구에 몰아도 손해가 없다.
- 이 경우 "상위 2N개의 도시를 선거구A, B로 N개씩 나누어 A와 B의 지지자 합이 모두 500N을 초과하도록 만들기" 가 된다.
- 무작위 두 도시 교환
- 답이 항상 존재하는 경우만 주어진다고 했으므로, 선거구 A, B에서 도시를 하나씩 뽑아 교환하고, 이 과정을 위 조건을 만족할 때까지 시도하는 방법으로 답을 구할 수 있다.
- 효율적인 탐색을 위해, 선거구 A, B의 지지자 수를 먼저 구해놓고 합이 500N보다 작은 선거구의 경우 보다 큰 값과 교환하도록 조건을 추가했다.
갑자기 무작위화가 튀어나와서 ????가 되버렸다. 휴리스틱 문제를 좀 풀어봐서 풀이가 납득이 가긴 하는데, 너무 갑자기 튀어나와서 당황했다. 괜히 P3이 아닌가?? 아무튼 그렇다. 위 내용을 그대로 구현하면 꽤 빠른 시간 내에 구할 수 있다.
후기
무작위화나 휴리스틱 문제들은 특히나 티어가 어느정도인지 감이 안잡혀서 기여를 못하겠다...
아무리 인터넷을 찾아봐도 에디토리얼을 찾을 수 없었다. 문제와 테스트케이스는 보이는데 에디토리얼만 보이지 않는다. 20년 전 문제라 그런가?
별개로, 무작위화 풀이 말고도 배낭 DP + 역추적 방법으로 푼 사람도 있는 것 같았다. 지지자 수를 무게로, 500N을 제한 무게로 볼 경우 0-1 배낭 문제가 되는 것 같다. 근데 인데 시간 내에 돌아가나?
코드
# 백준 2203
import io
import random
input = io.BufferedReader(io.FileIO(0), 1<<18).readline
def solve(N, city):
# 지지자 수 하위 N개 도시는 C로 고정
city.sort(reverse=True)
C = city[2*N:]
del city[2*N:]
# 골고루 분포하도록 A와 B를 섞기
random.shuffle(city)
A = city[:N]
B = city[N:]
sumA = 0
sumB = 0
for i in range(N):
sumA += A[i][0]
sumB += B[i][0]
target = 500*N
# 각 도시의 지지자 수가 N이 넘을 때까지 선거구 교환 반복
while sumA <= target or sumB <= target:
# 랜덤으로 두 도시를 뽑아 선거구 교환
iA = random.randint(0, N-1)
iB = random.randint(0, N-1)
# 교환하는 것이 이득일 경우 교환
if (sumA >= sumB and A[iA][0] > B[iB][0]) or (sumA < sumB and A[iA][0] < B[iB][0]):
sumA += B[iB][0] - A[iA][0]
sumB += A[iA][0] - B[iB][0]
A[iA], B[iB] = B[iB], A[iA]
return A, B, C
def main():
N = int(input())
city = []
for i in range(3*N):
c = int(input())
city.append((c, i+1))
A, B, C = solve(N, city)
for i in A:
print(i[1])
for i in B:
print(i[1])
for i in C:
print(i[1])
main()
