[프로그래머스] 완전범죄

문제

A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 단, 각 도둑이 물건을 훔칠 때 남기는 흔적이 누적되면 경찰에 붙잡히기 때문에, 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.

물건을 훔칠 때 조건은 아래와 같습니다.

• 물건 i를 훔칠 때,
  • A도둑이 훔치면 info\[i\]\[0\]개의 A에 대한 흔적을 남깁니다.
  • B도둑이 훔치면 info\[i\]\[1\]개의 B에 대한 흔적을 남깁니다.
• 각 물건에 대해 A도둑과 B도둑이 남기는 흔적의 개수는 1 이상 3 이하입니다.

경찰에 붙잡히는 조건은 아래와 같습니다.

• A도둑은 자신이 남긴 흔적의 누적 개수가 n개 이상이면 경찰에 붙잡힙니다.
• B도둑은 자신이 남긴 흔적의 누적 개수가 m개 이상이면 경찰에 붙잡힙니다.

각 물건을 훔칠 때 생기는 흔적에 대한 정보를 담은 2차원 정수 배열 info, A도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 n, B도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 m이 매개변수로 주어집니다. 두 도둑 모두 경찰에 붙잡히지 않도록 모든 물건을 훔쳤을 때, A도둑이 남긴 흔적의 누적 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 어떠한 방법으로도 두 도둑 모두 경찰에 붙잡히지 않게 할 수 없다면 -1을 return해 주세요.

예시

info	n	m	result
[[1, 2], [2, 3], [2, 1]]	4	4	2
[[1, 2], [2, 3], [2, 1]]	1	7	0
[[3, 3], [3, 3]]	7	1	6
[[3, 3], [3, 3]]	6	1	-1

조건

• 1 ≤ info의 길이 ≤ 40
  • info\[i\]는 물건 i를 훔칠 때 생기는 흔적의 개수를 나타내며, \[A에 대한 흔적 개수, B에 대한 흔적 개수\]의 형태입니다.
  • 1 ≤ 흔적 개수 ≤ 3
• 1 ≤ n ≤ 120
• 1 ≤ m ≤ 120

답

DP로 해결할 수 있습니다.

 

물건을 모두 훔쳤을 때 A의 흔적 합을 상태값으로, 그 때 B가 가질 수 있는 최소 흔적 합을 값으로 두는 1차원 배열을 준비합니다.

 

흔적 합은 최대 120까지 가질 수 있으므로, DP값의 초기값은 121(INF)으로 설정합니다.

 

단, 흔적 합 0은 불가능한 경우이므로 0입니다.

def solution(info, n, m):
    dp = [121] * n
    dp[0] = 0

각 물건 마다 두 가지 경우에 대해 DP를 업데이트 해야 합니다. 업데이트는 새로운 DP 배열인 NDP에서 진행하고, 업데이트가 모두 끝나면 이전단계 DP에 NDP를 덮어 씁니다.

 

경우 1. A가 물건을 훔칠 때 : 모든 DP 경우에 대해 t_a만큼 증가한 경우(ndp[i + t_a])를 업데이트합니다. B가 물건을 훔치지 않았기 때문에 B의 흔적합은 따로 증가하지 않습니다.

 

경우 2. B가 물건을 훔칠 때 : 모든 DP 경우에 대해 현재 상태(i)를 업데이트 합니다. B가 물건을 훔쳤으므로 B의흔적 합은 t_b만큼 증가합니다. 

def solution(info, n, m):
    # ...
    for t_a, t_b in info:
        ndp = [121] * n
        
        for i in range(n):
            if dp[i] == 121:
                continue
            # case 1.
            if i + t_a < n:
                ndp[i + t_a] = min(ndp[i + t_a], dp[i])
            # case 2.
            ndp[i] = min(ndp[i], dp[i] + t_b)
        
        dp = ndp

DP가 완성되면 A의 흔적합을 1부터 n까지 순회하며 최초로 B의 흔적합이 m보다 작아지는 경우를 찾습니다.

 

그 때의 A 흔적합 i를 반환하고, 그 값이 없다면 -1을 반환합니다.

def solution(info, n, m):
    ## ...
    for i in range(n):
        if dp[i] < m:
            return i
    return -1