문제 개요
N명의 도둑이 금고를 털려고 하는 상황을 가정해 봅시다. 금고를 지키던 경비원이 G만큼의 시간 동안 자리를 비웠다가 돌아옵니다. 각 도둑은 금고를 털는 데 걸리는 고유한 시간이 정해져 있으며, 동시에 금고 안에 들어갈 수 있는 인원은 최대 두 명입니다. 이때 확인해야 할 것은 도둑들이 경비원에게 들키지 않고 금고를 털 수 있는지 여부입니다. 판단할 때 다음 두 가지 규칙을 염두에 두어야 합니다.
- 한 도둑이 시간 t에 금고에 들어가고, 같은 시각 t에 다른 도둑이 나온다면, 두 사람은 실제로 동시에 금고 안에 있었던 것으로 간주하지 않습니다.
- 경비원이 시간 G에 금고로 들어오는 순간 어떤 도둑이 정확히 시간 G에 나온다면, 경비원은 그 도둑을 알아차리지 못합니다.
예를 들어 입력이 N = 3, G = 5, time = [3, 5, 2]라면 출력은 True가 됩니다. 다음과 같은 배치가 가능하기 때문입니다.
- t = 0일 때 첫 번째 도둑이 들어가서 t = 3에 나옵니다.
- t = 0일 때 두 번째 도둑이 들어가서 t = 5에 나옵니다.
- t = 3일 때 세 번째 도둑이 들어가서 t = 5에 나옵니다.
해결 접근 방법
이 문제는 부분집합 합(subset sum) 방식의 동적 계획법(DP)으로 해결할 수 있습니다. 동시에 최대 두 명까지 들어갈 수 있으므로, 전체 작업 시간을 두 그룹으로 나누어 각 그룹의 합이 G 이하가 되도록 만들 수 있는지를 확인하는 것이 핵심입니다. 구체적인 단계는 다음과 같습니다.
- time 리스트의 모든 원소의 합이 2*G보다 크면 False를 반환합니다. 두 명씩 교대로 들어가더라도 총 소요 시간이 허용 범위를 초과하기 때문입니다.
- 모든 원소의 합이 G 이하이면 True를 반환합니다. 한 명씩 차례대로 들어가도 충분히 가능합니다.
- 그 외의 경우에는 DP 배열을 활용합니다.
- 크기가 G+1인 배열 valid를 만들고 모든 값을 False로 초기화합니다.
- valid[0] := True로 설정합니다.
- time의 각 원소 x에 대해, i를 G부터 0까지 1씩 감소시키며 반복합니다.
- i - x >= 0이고 valid[i - x]가 True이면 valid[i] := True로 설정합니다.
- 마지막으로, time의 모든 원소의 합에서 valid[i]가 True인 i 중 최댓값을 뺀 결과가 G 이하이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
def solve(N, G, time):
if sum(time) > 2*G:
return False
elif sum(time) <= G:
return True
else:
valid = [False]*(G+1)
valid[0] = True
for x in time:
for i in range(G,-1,-1):
if i-x >= 0 and valid[i-x]:
valid[i] = True
if sum(time) - max(i for i in range(len(valid)) if valid[i]) <= G:
return True
else:
return False
N = 3
G = 5
time = [3,5,2]
print(solve(N, G, time))입력
3,5,[3,5,2]
출력
True