[프로그래머스] 도둑질 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

 

두 수를 인접하지 않게 선택하여 최대 합을 구하는 문제이다.

 

마을이 원형구조이므로 1, 2, 3, 4번 집이 있을 때,

1번은 2번, 4번과 인접해있다.

 

따라서 1번을 선택할 때의 경우(2, 4번은 선택불가)와 1번을 선택하지 않을 경우(1번만 사용불가)를 나누어서

두 결과값 중 최대를 반환하면 된다.

 

 

구현 언어: Python

 

def solution(money):
    # 3 1 4 7 2 5
    case1 = [i for i in money]
    case2 = [i for i in money]
    # 첫 번째를 선택하는 경우
    case1[1], case1[-1] = case1[0], 0
    # 첫 번째를 선택하지 않는 경우
    case2[0] = 0
    
    for i in range(2, len(money)):
        case1[i] = max(case1[i-1], case1[i-2] + case1[i])
        case2[i] = max(case2[i-1], case2[i-2] + case2[i])
    
    # print(f'case1: {case1}')
    # print(f'case2: {case2}')
    
    return max(case1[-1], case2[-1])

 

여기서, 제출했을 때 계속해서 1번 케이스만 틀리는 문제가 발생했다.

커뮤니티에 다른 분들이 올려주신 댓글을 확인해보니 나는 이전(i-1)과 그 이전(i-2)를 체크하는데,

 

10 0 0 1000 10 2 와 같은 경우 올바른 결과를 찾아내지 못하는 걸 발견했다.

 

위 예제에서 10를 선택하는 경우, 두 번째인 0과 마지막인 2를 0으로 초기화했었는데

두 번째 값인 0을 첫 번째와 같은 값인 10으로 만들어서 첫 번째 값의 손실을 해결할 수 있었다.