[프로그래머스] 도둑질

문제 정보

• 프로그래머스 문제 링크
• 난이도 : level 4

 

해결 방법

현재까지 확인한 idx 번째 집에서 털 수 있는 돈의 최댓값을 dict 에 key-value 형태로 저장했습니다. 집 사이의 간격은 최대 3칸이 될 수 있어서 헷갈렸는데 ( 아래 이미지에 고뇌의 흔적이 보입니다. ) 현재까지 확인한 이라는 조건이 붙기 때문에 방범장치가 영향을 줄 수 있는 2칸만 확인하면 됩니다. 점화식으로는 아래와 같이 나타낼 수 있습니다. 

newDp = max(memoization1[idx - 1], memoization1[idx - 2] + money[idx])

그리고 첫 번째 ( idx 값으로는 0 ) 집을 털지 여부를 판단하기 위해 selZero 라는 변수로 판단했습니다. 첫 번째 집을 털게 되면 마지막 집을 털지 못하기 때문입니다. 이것 때문에 계산식을 따로 둘 수 밖에 없는데 왜냐하면 어떤 집을 털지를 확인하는건 앞에서부터 계산이 필요하고 집이 동그랗게 배치되어 있기 때문에 어디에서 시작을 하더라도 같기 때문입니다.

소스 코드

1st TRY

# top-down 방식으로 풀 경우 재귀 제한 (1,000) 초과 : 1,000,000
def solution(money):
    answer = 0
    memoization = {} # key : idx / value : dp[idx]
    
    # idx 번째 집까지 털었을 경우 최대 값
    # 1. idx 0 선택   : idx <= len(money) - 2
    # 2. idx 0 선택 X : idx <= len(money) - 1
    def dp(idx, selZero):
        
        # 종료 조건
        if idx == 1:
            if selZero:
                memoization[idx] = money[0]
            else :
                memoization[idx] = money[1]
        
        if idx == 2:
            if selZero :
                memoization[idx] = money[0] + money[2]
            else :
                memoization[idx] = max(money[1], money[2])
        
        if(idx not in memoization):
            newDp = max(dp(idx - 1, selZero), dp(idx - 2, selZero) + money[idx])
            memoization[idx] = newDp
            
        return memoization[idx]

    
    yesSelzero = dp(len(money) - 2, True)
    memoization = {}
    noSelzero = dp(len(money) - 1, False)
    answer = max(yesSelzero, noSelzero)

    return answer

파이썬의 재귀 제한 값인 1,000 을 초과해서 통과를 하지 못했습니다. 값을 변경하는 방법이 있었지만 시간 초과로 실패했습니다. 재귀 호출을 적게 사용 하도록 Top-Down 방식에서 Bottom-Up 방식으로 변경하여 다시 시도했습니다.

2nd TRY

# bottom-up
# 시간 초과
def solution(money):
    answer = 0
    memoization = {}
    
    def dp(idx, selZero):
        
        # 종료 조건
        if idx == 1:
            if selZero:
                memoization[idx] = money[0]
            else :
                memoization[idx] = money[1]
        
        if idx == 2:
            if selZero :
                memoization[idx] = money[0] + money[2]
            else :
                memoization[idx] = max(money[1], money[2])
        
        # 다음 dp 구하기
        if(idx not in memoization):
            newDp = max(dp(idx - 1, selZero), dp(idx - 2, selZero) + money[idx])
            memoization[idx] = newDp
            
        return memoization[idx]

    # bottom-up 방식으로 0 번째 집 선택하는 경우 구하기
    for idx in range(1, len(money) - 1):
        dp(idx, True)
    
    yesSelzero = memoization[len(money) - 2]
    
    # bottom-up 방식으로 0 번째 집 선택하지 않는 경우 구하기
    memoization = {}
    for idx in range(1, len(money)):
        dp(idx, False)
    
    noSelzero = memoization[len(money) - 1]
    
    # 둘 중 큰 수 구하기
    answer = max(yesSelzero, noSelzero)
    return answer

시간 초과로 실패하여 아래쪽 반복문을 제거하니 답은 틀렸지만 시간 초과가 나지는 않아 반복문의 갯수가 문제인줄로 알고 1개로 줄이려고 했지만 앞에서 말했듯이 첫 번째 집을 선택하느냐에 따라 계산은 두 번해야 합니다.

3rd TRY

# bottom-up & 불필요 함수 제거
# 위의 방법에서 반복문을 사용할 경우 불필요하게 dp 함수를 호출하여 시간초과가 된다.
# dp 호출시 max 부분에서 dp 를 2번 더 호출 하기 때문으로 보인다.
# 여기서도 반복문을 한번 더 사용할 경우 O(2N) -> O(3N) 일부 케이스에서 시간 초과가 된다.
def solution(money):
    answer = 0
    memoization1 = {}
    memoization2 = {}
    
    # bottom-up 방식으로 0 번째 집 선택하는 경우 구하기
    for idx in range(1, len(money) - 1):
        if idx == 1:
            memoization1[idx] = money[0]
        elif idx == 2:
            memoization1[idx] = money[0] + money[2]
        else :
            # 다음 dp 구하기
            newDp = max(memoization1[idx - 1], memoization1[idx - 2] + money[idx])
            memoization1[idx] = newDp
    
    yesSelzero = memoization1[len(money) - 2]
    
    # bottom-up 방식으로 0 번째 집 선택하지 않는 경우 구하기
    for idx in range(1, len(money)):
        if idx == 1:
            memoization2[idx] = money[1]
        elif idx == 2:
            memoization2[idx] = max(money[1], money[2])
        else :
            # 다음 dp 구하기
            newDp = max(memoization2[idx - 1], memoization2[idx - 2] + money[idx])
            memoization2[idx] = newDp
    
    noSelzero = memoization2[len(money) - 1]
    
    # 둘 중 큰 수 구하기
    answer = max(yesSelzero, noSelzero)
    return answer

결국 반복문의 수는 그대로 두고 불필요하게 호출한 함수만 제거했습니다. 두 번째 풀이와 같이 시간 복잡도는 동일하게 O(N) 이지만 문제 자체의 시간 제한이 좀 빡빡한 것 같았습니다.

 

참고 자료

• [프로그래머스] 도둑질, 파이썬
• [Python] 파이썬 재귀 함수 제한 풀기 / 파이썬 최대 재귀 제한 해제