| 시간 제한 | 메모리 제한 |
| 1초 | 128MB |
문제
학생회장을 하고 있는 상근이는 이번 학교 축제 행사로 학우들간의 친밀감을 돈독히 하고자 줄다리기를 하려 한다.
하지만 이 줄다리기에 형평성을 최대한 고려하기위해 두 팀간의 사람 수 차이를 1 이하로 하려하며, 두 팀간의 몸무게의 차이가 최소화되도록 하고자 한다.
이때 상근이가 나누려 하는 두 팀의 몸무게를 각각 출력 하시오.
입력
가장 첫 번째 줄에 줄다리기를 하기 원하는 총 인원의 수(1 ≤ N ≤ 100)가 주어진다.
이후 N개의 줄에 줄다라기에 참여하기 원하는 사람의 몸무게(1 ≤ K ≤ 450)가 주어진다.
출력
두팀의 몸무게를 작은 순서대로 순차적으로 출력한다.
풀이
N명이 주어졌을 때, 한 팀에 있을 수 있는 최대 인원은 N//2명 또는 N//2+1명이다. 여기서 전체 인원의 몸무게 총합을 아 수 있기 때문에 N이 홀수인 경우, N//2명의 몸무게를 구해서 몸무게 총합에서 빼주면 N//2+1명의 몸무게를 바로 얻을 수 있다. 따라서 홀수, 짝수 여부와 관련 없이 문제를 N//2명의 몸무게 합으로 해결할 수 있다.
N//2명의 몸무게는 최대 N//2 * 450일 수 있다. 더 빠른 탐색을 위해 범위를 더 좁혀줄 수도 있다. 전체 몸무게가 t일 때, 한 팀의 몸무게는 t//2에 근접할 것이다. 이것을 이상치라고 하면 최적해와 이상치의 큰 차이는 최대 몸무게를 가진 1명만큼의 무게와 같거나 클 수 없다. 3명의 몸무게가 모두 최대 몸무게인 450이라고 하면 최적해는 이상치와 225의 차이를 갖는다. 따라서 문제에서 얻어야 하는 해는 t//2 + 225 내에 반드시 존재한다고 할 수 있다.
만약 3명으로 무게 10인 팀을 만들었다고 하면, 무게가 5인 사람이 1명 추가되어 4명으로 무게가 15인 팀을 만들 수 있다. 0명으로부터 시작해서 모든 사람들의 몸무게를 확인하며 사람 수(n)로 구성 가능한 몸무게(w)를 dp[n][w]라고 하면 아래와 같이 표현된다.
노란 칸은 dp[3][2]이고 3명으로 2의 몸무게를 만들 수 있는지 여부를 저장하는 공간이 된다. 0명으로 무게 0은 구성 가능하기 때문에 dp[0][0]은 1로 초기화하고 나머지 값은 모두 0으로 초기화한다.
이제 순차적으로 한 사람씩 꺼내어 몸무게를 확인한다. 이번에 확인할 사람의 몸무게가 k일 때, dp[n][w]가 만약 1이라면 dp[n+1][w+k] 역시 1이 된다. 모든 사람에 대해 이 과정을 거치면 dp[n][w]는 n명으로 w의 몸무게를 구성할 수 있는지 여부가 된다. 마지막으로 절반 인원으로 구성되는 배열 dp[N//2][w](w는 1부터 가능한 최대 몸무게까지)를 확인해 1인 곳에 대하여 t-w*2의 절댓값을 확인한다. 한 팀으로 구성된 몸무게가 w이면 나머지 한 팀의 몸무게는 t-w가 된다. 둘의 차이는 t-w-w의 절댓값이므로 이 값을 확인해 가장 작은 경우만 남기면 된다.
dp[n][w] 배열을 구성하는 탐색에서 주의해야 할 점이 한 가지 있는데 탐색 방향이 빨간색으로 진행되는 경우, 몸무게가 3인 사람에 대해 dp[2][2]가 1이라면 dp[3][5]가 1이 되고 연쇄적으로 dp[4][8], dp[5][11], ...이 1이 된다. 같은 사람이 팀에 여러 번 반복해 들어가는 것이기 때문에 탐색을 역순으로 파란색처럼 역순으로 진행해야 이런 오류가 없게 된다.
아래는 이 풀이를 살짝 응용한 문제. 거의 같은 풀이가 적용된다.
26607번: 시로코와 은행털기
첫 번째 줄에 사람의 수 $n$와 뽑을 인원 $k$, 그리고 힘과 스피드 수치의 합 $x$가 공백으로 구분되어 주어진다. 그 다음줄부터 $n$개의 줄에는 각 사람들이 지닌 힘과 스피드 능력치 $a$ $b$가 주어
www.acmicpc.net
정답 코드
import sys
input = sys.stdin.readline
N = int(input())
K = [int(input()) for _ in range(N)]
total = sum(K) # 총 몸무게
gap = total # 팀 간 몸무게 차이(최대값인 총 몸무게로 초기화)
half = N // 2 # 팀 인원
# 배열 초기화
dp = [[0] * (total//2+225) for _ in range(half + 1)]
dp[0][0] = 1
for n in K:
for i in range(half,0,-1): # 탐색을 배열 끝에서 1까지 역순으로 진행
for k in range(n,total//2+225):
# 탐색 중인 사람의 몸무게를 뺀 팀이 존재하면 1명 추가한 팀도 있다.
if dp[i-1][k-n]:
dp[i][k] = 1
continue
a = 0
for k in range(total//2+225):
if dp[half][k]:
if gap > abs(total-k*2):
gap = abs(total-k*2)
a = k
if a>total-a:
a = total - a
print(a, total-a)
