[코딩테스트] 프로그래머스 - 완전범죄(Lv.2)

https://school.programmers.co.kr/learn/courses/30/lessons/389480

프로그래머스

 

1. 문제 요약

<입력>

▫️info: 2차원 정수 배열, 각 물건을 훔칠 때 생기는 흔적 정보

▫️n: A가 검거되는 최소 흔적 개수

▫️m: B가 검거되는 최소 흔적 개수

 

<출력>

▫️A가 남긴 누적 흔적 개수의 최솟값

▫️모든 물건을 훔칠 수 있는 경우가 존재하지 않을 경우에는 -1

 

<제한사항>

▫️1 ≤ info의 길이 ≤ 40
▫️info[i]는 물건 i를 훔칠 때 생기는 흔적의 개수, [A에 대한 흔적 개수, B에 대한 흔적 개수]의 형태
▫️1 ≤ 흔적 개수 ≤ 3
▫️1 ≤ n ≤ 120
▫️1 ≤ m ≤ 120

 

🚨즉, 모든 물건을 도둑 A, B가 나눠서 훔쳐야 하고, 검거되지 않으면서 A의 흔적을 최소화해야 하는 문제

 

---

2. 핵심 아이디어(정답)

- 가능한 모든 경우를 탐색하면서 A의 흔적이 최소가 되도록 해야 함
   → 모든 경우를 다 해보면 너무 오래 걸리므로 DP(Dynamic Programming) 사용

def solution(info, n, m):
	# i번째 물건까지 고려했을 때, A의 누적 흔적이 a & B의 누적 흔적이 b인 경우의 가능 여부 기록
    # n, m은 각각 A와 B의 최대 흔적 개수
    dp = [[[False] * m for _ in range(n)] for _ in range(len(info) + 1)]
    
    # 시작 상태 : 아직 아무 물건도 훔치지 않았으며, A도 B도 흔적이 0인 상태(항상 가능) 
    dp[0][0][0] = True
    
    # DP를 채우는 과정
    # (1) A가 훔치면 A의 흔적 += info[i][0]
    # (2) B가 훔치면 B의 흔적 += info[i][1]
    # (3) 위의 과정 반복
    for i, (a_info, b_info) in enumerate(info):
        for a in range(n):
            for b in range(m):
                if dp[i][a][b]:
                    # A가 훔치는 경우
                    na = a + a_info  # 흔적 누적
                    if na < n:
                        dp[i + 1][na][b] = True
                    
                    # B가 훔치는 경우
                    nb = b + b_info  # 흔적 누적
                    if nb < m:
                        dp[i + 1][a][nb] = True

    # 마지막 단계에서 가능한 조합 중 A의 흔적이 가장 작은 값 찾기
    for a in range(n):
        for b in range(m):
        	# 모든 물건을 훔친 경우 중 가능한 케이스에서 a 최소인 경우 찾기
            if dp[len(info)][a][b]:
                return a
    return -1

✔️ DP 배열 : dp[i][a][b] 
▫️의미: i번째 물건까지 고려했을 때, A의 누적 흔적이 a & B의 누적 흔적이 b인 경우의 가능 여부 기록
▫️시작 상태:

    - dp[0][0][0] = True
    - 아직 아무 물건도 훔치지 않았으며, A도 B도 흔적이 0인 상태(항상 가능) 

▫️DP를 채워가는 과정
    (1) A가 훔치면 A의 흔적 += info[i][0]
    (2) B가 훔치면 B의 흔적 += info[i][1]
    (3) 위의 과정 반복
     Example)
          i = 0, info[0] = (2, 1)
          현재 dp[0][0][0] = True
          (1) A가 훔치면 A 흔적 2, B 흔적 0 -> dp[1][2][0] = True
          (2) B가 훔치면 A 흔적 0, B 흔적 1 -> dp[1][0][1] = True

▫️마지막 값 반환

    - 모든 물건을 다 훔쳤을 때, 가능한 모든 조합 중에서 A의 흔적 a가 가장 작은 값을 반환

    - a를 0부터 시작하므로, 가능한 조합(dp가 true인 경우) 중에서 가장 작은 a값을 만나자마자 바로 return
    => len(info)번째 물건까지 고려했을 때 True인 경우 == 모든 물건을 훔친 경우 중 가능한 케이스

---

3. 틀린 이유 분석

✅ 개념 부족

DP에 대한 개념을 몰랐음(처음 풀어봤음 ㅠ)

---

4. DP(동적 계획법)

복잡한 문제를 간단한 여러 개의 문제로 나눠 푸는 방법

ex) 100번째 피보나치 수 = (99번째 피보나치 수 + 98번째 피보나치 수) 이므로, 이전 피보나치 수를 구하여 풀 수 있음

즉, 부분 문제에 대한 답을 구하고 이를 이용하여 더 큰 문제의 답을 구하는 과정을 반복 → 최종 답까지 도달하는 것 

 

❓언제 DP를 사용하는가?

- 어떤 항을 구하기 위한 전 항들을 완벽히 구할 수 있고, 그 항들을 이용하여 정의에 맞는 현재 항이 깔끔하게 정의될 때

 

❓어떻게 DP 문제를 풀어야 하는가?

- 문제 탐색 →  DP식 세우기 → 검증 및 구현 의 순서

- 이 중 문제 탐색과 DP식 세우는데 80%는 사용하게 됨

 

(1) 반복문 (bottom-up 방식)

F = [0] * (n + 1)
F[0] = 0
F[1] = 1
for i in range(2, n + 1):
    F[i] = F[i-1] + F[i-2]

(2) 재귀 + 메모이제이션 (top-down 방식)

def fib(n):
    if n <= 1:
        return n
    if dp[n] != -1:
        return dp[n]
    dp[n] = fib(n-1) + fib(n-2)
    return dp[n]

dp = [-1] * (n + 1)
print(fib(n))

 

# 참고 블로그:

https://stonejjun.tistory.com/23 

https://asn6878.tistory.com/19

프로그래머스 - 완전범죄

 

# 추천 문제

https://stonejjun.tistory.com/24

좋은 DP 문제들 추천