[프로그래머스] 완전 범죄 (Level 2)

문제 요약

A도둑과 B도둑이 모든 물건을 훔치려고 한다.

각 물건을 훔칠 때는 둘 중 한 명이 훔쳐야 하며, 누가 훔치느냐에 따라 남기는 흔적의 개수가 다르다.

• A도둑이 물건 i를 훔치면 info[i][0]개의 A 흔적을 남긴다.
• B도둑이 물건 i를 훔치면 info[i][1]개의 B 흔적을 남긴다.

단, 각 도둑의 흔적이 일정 개수 이상 누적되면 경찰에 붙잡힌다.

• A도둑의 흔적이 n개 이상이면 실패
• B도둑의 흔적이 m개 이상이면 실패

모든 물건을 훔치면서 두 도둑 모두 잡히지 않도록 해야 한다.

이때 가능한 경우 중 A도둑이 남긴 흔적의 최솟값을 구해야 한다.
불가능하다면 -1을 반환한다.

문제 조건

1 <= len(info) <= 40
1 <= info[i][0], info[i][1] <= 3
1 <= n <= 120
1 <= m <= 120

물건의 개수는 최대 40개이므로 모든 경우를 단순히 탐색하면 2^40이 되어 불가능하다.

따라서 동적 계획법, 즉 DP를 사용해야 한다.

접근 방법

각 물건마다 선택지는 두 가지다.

1. A도둑이 훔친다.
2. B도둑이 훔친다.

우리가 최종적으로 최소화해야 하는 값은 A도둑의 흔적이다.

하지만 B도둑도 흔적이 m 이상이 되면 안 되므로, B도둑의 흔적 상태를 기준으로 DP를 구성할 수 있다.

점화식

각 물건마다 A가 훔치는 경우와 B가 훔치는 경우를 처리한다.

현재 물건의 흔적 정보가 다음과 같다고 하자.

a_trace, b_trace

1. A도둑이 훔치는 경우

A도둑의 흔적이 증가한다.

new_a = dp[b] + a_trace

단, A도둑의 흔적이 n 이상이면 경찰에 잡히므로 제외한다.

if new_a < n:
    next_dp[b] = min(next_dp[b], new_a)

B도둑이 훔친 것이 아니므로 B 흔적 b는 그대로 유지된다.

2. B도둑이 훔치는 경우

B도둑의 흔적이 증가한다.

new_b = b + b_trace

단, B도둑의 흔적이 m 이상이면 경찰에 잡히므로 제외한다.

if new_b < m:
    next_dp[new_b] = min(next_dp[new_b], dp[b])

A도둑이 훔친 것이 아니므로 A 흔적은 그대로 유지된다.

전체 코드

def solution(info, n, m):
    INF = 10**9

    dp = [INF] * m
    dp[0] = 0

    for a_trace, b_trace in info:
        next_dp = [INF] * m

        for b in range(m):
            if dp[b] == INF:
                continue

            new_a = dp[b] + a_trace
            if new_a < n:
                next_dp[b] = min(next_dp[b], new_a)

            new_b = b + b_trace
            if new_b < m:
                next_dp[new_b] = min(next_dp[new_b], dp[b])

        dp = next_dp

    answer = min(dp)

    return answer if answer != INF else -1

예시로 이해하기

예를 들어 현재 상태가 다음과 같다고 하자.

dp[2] = 5

이는 현재까지 훔친 결과,

• B도둑 흔적은 2
• A도둑 흔적은 5

라는 뜻이다.

이번 물건의 정보가 다음과 같다면,

[a_trace, b_trace] = [3, 2]

선택지는 두 가지다.

A도둑이 훔치는 경우

A 흔적 = 5 + 3 = 8
B 흔적 = 2

A 흔적이 n보다 작다면 가능한 상태다.

B도둑이 훔치는 경우

A 흔적 = 5
B 흔적 = 2 + 2 = 4

B 흔적이 m보다 작다면 가능한 상태다.

이런 방식으로 모든 물건에 대해 가능한 상태를 갱신한다.

시간 복잡도

물건의 개수를 k, B도둑 흔적 제한을 m이라고 하면 DP의 시간 복잡도는 다음과 같다.

O(k * m)

제한 조건에서

k <= 40
m <= 120

이므로 충분히 빠르게 해결할 수 있다.

공간 복잡도는 DP 배열 하나의 크기가 m이므로

O(m)

이다.

정리

이 문제는 모든 물건에 대해 A 또는 B를 선택해야 하므로 처음에는 완전 탐색처럼 보인다.

하지만 단순 완전 탐색은 경우의 수가 너무 많다.

핵심은 다음과 같다.

• B도둑의 누적 흔적을 DP의 상태로 둔다.
• 각 B 흔적 상태에서 가능한 최소 A 흔적을 저장한다.
• A나 B가 경찰에 잡히는 상태는 제외한다.
• 마지막에 가능한 상태 중 A 흔적의 최솟값을 반환한다.

즉, 이 문제는 B 흔적을 제한으로 두고 A 흔적을 최소화하는 DP 문제로 볼 수 있다.