도둑질

Dynamic programming

def solution(money):
    answer = 0
    
    dp = [0 for i in range(1000000)]
    
    for i in range(len(money)):
        dp[i] = money[i]
    
    for i in range(len(money)):
        dp[i] = max(dp[i - 1], dp[i - 2] + money[i])
        result = dp[i]
    
    return result

• 문제 : 이 경우는 첫집과 마지막 집을 동시에 털 수 있다는 것이다. 첫집과 마지막집은 연결되어 있기에 동시에 털 수 없다. 따라서 경우를 2가지로 나누어 야한다.

  1. 첫집은 털고 마지막 집은 털지 않는 경우

  2. 첫집은 털지 않고 마지막 집은 터는 경우

     -> 최대가 되야 하므로 첫집도 털지 않고, 마지막 집도 털지 않는 경우는 없다.

import copy

def solution(money):
    answer = 0
    
    dp_1 = [0 for i in range(1000000)]
    
    # 경우 1 : 첫집은 털고, 마지막 집은 털지 않는 경우
    dp_1[0] = money[0]
    dp_1[1] = 0
    for i in range(2, len(money)):
        dp_1[i] = max(dp_1[i - 1], dp_1[i - 2] + money[i])
        if i == len(money) - 1:
            case_1 = dp_1[i]
            break
            
    dp_2 = [0 for i in range(1000000)]
    
    # 경우 2 : 첫집은 털지 않고, 마지막 집은 터는 경우
    dp_2[0] = 0
    dp_2[1] = money[1]
    for i in range(2, len(money)):
        dp_2[i] = max(dp_2[i - 1], dp_2[i - 2] + money[i])
        case_2 = dp_2[i]
    
    result = max(case_1, case_2)
    return result

• 다음과 같이 수정했으나, 잘 되지 않는 이유를 보니, dp[0]와 dp[1]일때 값이 정해져 있지 않아서 그런가 보다…..
• 그래서, 혹시 dp_1 이든 dp_2이든 배열의 최대값을 구해야했나?라고 생각했는데

import copy

def solution(money):
    answer = 0
    
    dp_1 = [0 for i in range(1000000)]
    
    # 경우 1 : 첫집은 털고, 마지막 집은 털지 않는 경우
    dp_1[0] = money[0]
    dp_1[1] = max(money[0], money[1])
    for i in range(2, len(money)):
        dp_1[i] = max(dp_1[i - 1], dp_1[i - 2] + money[i])
            
    dp_2 = [0 for i in range(1000000)]
    
    # 경우 2 : 첫집은 털지 않고, 마지막 집은 터는 경우
    dp_2[0] = 0
    dp_2[1] = money[1]
    for i in range(2, len(money)):
        dp_2[i] = max(dp_2[i - 1], dp_2[i - 2] + money[i])
    
    result = max(max(dp_1), max(dp_2))
    return result

• 이것도 잘 안되네…. 무슨 문제야..

def solution(money):

    dp_1 = [0 for i in range(len(money))]
    
    # 경우 1 : 첫집은 털고, 마지막 집은 털지 않는 경우
    dp_1[0] = money[0]
    dp_1[1] = max(money[0], money[1])
    for i in range(2, len(money) - 1):
        dp_1[i] = max(dp_1[i - 1], dp_1[i - 2] + money[i])
            
    dp_2 = [0 for i in range(len(money))]
    
    # 경우 2 : 첫집은 털지 않고, 마지막 집은 터는 경우
    dp_2[0] = 0
    dp_2[1] = money[1]
    for i in range(2, len(money)):
        dp_2[i] = max(dp_2[i - 1], dp_2[i - 2] + money[i])
    
    result = max(max(dp_1), max(dp_2))
    return result

• 결국엔 문제를 찾았다… 경우1에서 마지막집을 털어버렸다. 털면 안됬었는데… ㅋㅋㅋㅋ