[Programmers/Python] 완전범죄

1. 문제 파악하기

• 모든 물건을 훔쳐야 한다.
• 각 물건은 훔칠 때마다 a/b 두 도둑 중 하나가 흔적을 남긴다.
• a의 흔적 합이 n 이상이면 a가, b의 흔적이 m이상이면 b가 잡힌다.
• 목표는 "둘 다 잡히지 않으면서" a의 흔적 합을 최소화하는 것

1. 각 물건마다 선택(a가 훔칠까, b가 훔칠까)을 해야하고,
2. 전체 선택 결과에 대해 두 변수(=a의 흔적, b의 흔적)가 제약(<= n, <=m)을 지켜야하며
3. 그 중 a의 흔적을 최소화 해야한다
   => 전형적인 DP(동적 계획법) 문제 형태

---

2. DP 상태(메모이제이션) 설계

• dp[k] = 지금까지 b 의 흔적 합이 정확히 k 일 때, a의 흔적 합의 최소값
• 배열 길이는 m (b가 잡히지 않으려면 k < m 까지만 의미 있음)
• 초기값

INF = 10**9
dp = [INF]*m
dp[0] = 0 # b가 0 흔적일 때 a도 0

 

• 이제 물건을 하나씩 순회하며 새로운 new_dp 를 만든 뒤
  • a가 훔치기 전이
    • b의 흔적 변화 없음 => 인덱스 j 그대로
    • a 흔적은 dp[j] + info[i][0]
  • b가 훔치기 전이
    • b 흔적이 j + info[i][1] => 이 값이 m 미만일 때만 유효
    • a 흔적은 dp[j] 그대로
  • 전이할 때마다
    • a의 흔적이 n 이상이 되면 -> a가 잡히므로 무시
    • b의 흔적이 m 이상이 되면 -> b가 잡히므로 무시

---

3. 전이 수식 한눈에 보기

for each item i with (a_trace, b_trace):
    new_dp = [INF]*m
    for j in range(m):            # j = 이전까지 b 흔적
        if dp[j] == INF: continue
        # 1) a가 훔칠 경우
        na = dp[j] + a_trace
        if na < n:
            new_dp[j] = min(new_dp[j], na)

        # 2) b가 훔칠 경우
        nb = j + b_trace
        if nb < m:
            new_dp[nb] = min(new_dp[nb], dp[j])

    dp = new_dp

• new_dp[j] 에 들어가는 값은 "새로 a가 남긴 흔적의 최소 합"
• new_dp[nb] 에는 "b쪽으로 전이했을 때의 a 흔적(=이전 dp[j])"을 넣어 준다

 

4. 최종 결과 구하기

• 모든 물건을 처리한 뒤 dp 배열에 유한값(!= INF)으로 남아 있는 인덱스들 중
  • min(dp)가 우리가 찾는 "두 도둑 다 잡히지 않으면서 a 흔적을 최소화한 값"
• 만약 min(dp) == INF 이면 -> 불가능 -> -1 반환

---

5. 코드 구현

def solution(info, n, m):
    INF = 10**9
    # dp[j] = b가 남긴 흔적이 j일 때, a의 흔적 최소값
    dp = [INF] * m
    dp[0] = 0

    for a_trace, b_trace in info:
        new_dp = [INF] * m
        for j in range(m):
            if dp[j] == INF:
                continue
            # 1) a가 훔칠 경우
            na = dp[j] + a_trace
            if na < n:           # a가 잡히지 않으려면 흔적 < n
                if na < new_dp[j]:
                    new_dp[j] = na

            # 2) b가 훔칠 경우
            nb = j + b_trace
            if nb < m:           # b가 잡히지 않으려면 흔적 < m
                if dp[j] < new_dp[nb]:
                    new_dp[nb] = dp[j]

        dp = new_dp

    ans = min(dp)
    return ans if ans < INF else -1

---

6. 이렇게 생각한 이유

1. "둘 다 잡히지 않는다" = 두 개의 누적 합에 대한 제약
2. 모든 물건을 선택해야 하니, 각 물건마다 선택지를 두고 모든 조합을 고려해야 한다
3. 조합이 많으면 탐색이 터지니 -> DP 사용
4. DP 차원은 (물건 인덱스, a 합, b 합) 이나,
   • a 합과 b 합 둘 다 상태로 쓰면 3차원
   • 원하는 건 b 합 상태별로 a 합 최소값 -> 2차원 -> 1차원으로 압축 가능
5. 전형적인 0/1 배낭(knapsack) 변형 형태로 보고,
   • b합 을 배낭 용량 인덱스 j로,
   • a합을 배낭에 들어간 무게(=최소값)로 다루면 자연스럽게 1차원 DP로 가능