[Python 문제 풀이] 프로그래머스 "완전 범죄"

진짜 오랜만에 코딩테스트 풀어봤다. 이 문제는 누산해가는 전형적인 dp문제이다. 쉬울 줄 알았는데 감이 다 죽었는지, 어려워서 결국 딥시크한테 힌트 달라고 했다. 참고로 같은 문제를 ChatGPT는 풀지 못했다!

 

의사코드

 

1. info에 대해서 반복(2~4)

2.     ckpt에 대해 반복

3.         A와 B가 훔치는 두 경우의 수를 n_ckpt에 기록한다.

4.     ckpt를 n_ckpt로 업데이트한다.

 

코드

 

def solution(info, n, m):
    ckpt = {0:0}
    for x, y in info:
        n_ckpt = {}
        for xx, yy in ckpt.items():
            if xx + x < n:
                if xx + x not in n_ckpt or n_ckpt[xx+x] > yy:
                    n_ckpt[xx + x] = yy
            if yy + y < m:
                if xx not in n_ckpt or n_ckpt[xx] > yy + y:
                    n_ckpt[xx] = yy + y
        if n_ckpt:
            ckpt = n_ckpt
        else:
            return -1
    return min(ckpt.keys())

각 단계별로 최소의 Y 누적합만을 선택

def solution(info, n, m):
    ckpt = set([(0,0)])
    for x, y in info:
        n_ckpt = set()
        for xx, yy in ckpt:
            if xx + x < n:
                n_ckpt.add((xx+x,yy))
            if yy + y < m:
                n_ckpt.add((xx,yy+y))
        if n_ckpt:
            ckpt = n_ckpt
        else:
            return -1
    return min(A for A, _ in ckpt)

각 단계에서 중복만 확인하고 최소인 경우 뿐만 아니라 모든 경우를 기록함. (시간복잡도 증가)