[프로그래머스/파이썬] 도둑질

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

앞서 포도주문제랑 계단오르기 그 외 RGB문제 등을 풀면서 DP를 좀 익히고 풀었다.

그래서 그런지 생각보다 빨리 풀렸음..! 역시 연습이 답이다

프로그래머스

문제 요약 : 그림과 같이 집이 원형으로 배치된 마을이 있다. 인접된 집은 방범장치가 있어 두 집을 연속해서 털면 경보가 울린다. 도둑이 집을 털려고 할 때에 방법장치를 울리지 않고 훔칠 수 있는 돈의 최대값을 구하라.

시도 1 )

집은 무조건 3개 이상 주어지기 때문에 if문을 이용하지 않고

dp[0] = money[0]

dp[1] = max(money[0],money[1])로 해주고 2부터 돌아가도록 하였다.

이 문제에서는 따로 도착지점을 선택하지 않았기 때문에 그냥 가장 큰 값을 구할 수 있도록 dp[i]를 구할 때 dp[i-1]도 비교해가면서 풀었다.

 

그 이유는

https://eunsun-zizone-zzang.tistory.com/10?category=1073600 

[백준/파이썬] 2156 : 포도주 시식

포도주 시식문제에서 자세히 적어놨음...^_^

 

암튼, 그렇게 했는데 여기서 중요한 점은 마을이 원형이기 때문에 첫번째 집과 마지막 집이 인접하다는 것이다.

낭창하게 len(money)가 홀수일 경우에만 겹칠 것이라 생각하여 아래와 같이 코드를 짰다.

def solution(money):
    n = len(money)
    dp = [0]*n
    dp[0] = money[0]
    dp[1] = max(money[1],money[0])
    
    for i in range(2,n):
        if (i == n-1 and n%2 == 1):
            dp[i] = max(dp[i-1],dp[i-2]+money[i]-min(money[i],money[0]))
        else :
            dp[i] = max(dp[i-1], dp[i-2] + money[i])
    
    return dp[n-1]

이러면 55점짜리 실패가 나온다..

 

시도 2 )

생각해보니 마지막에 홀수짝수가 문제되지 않을 것 같았다.

왜냐면 어차피 dp값을 비교할 때에 dp[i-1]를 비교해주기 때문이다.

그래서 홀수인지 알아보는 코드를 빼고 그냥 전부다 money[i]와 money[0]중 더 작은 것을 빼주는 것으로 해주었다.

def solution(money):
    n = len(money)
    dp = [0]*n
    dp[0] = money[0]
    dp[1] = max(money[1],money[0])
    
    for i in range(2,n):
        if i == n-1:
            dp[i] = max(dp[i-1],dp[i-2]+money[i]-min(money[i],money[0]))
        else :
            dp[i] = max(dp[i-1], dp[i-2] + money[i])
    
    return dp[n-1]

이러면 65점됨 ㅎㅎ

 

풀이 )

마지막에 money[n-1]값은 더해주지만, money[0]값은 더해줬는지 아닌지 모름

위에서 생각한 대로 문제는 두가지로 나눌 수 있다. money[0]을 더해주는 값과 money[n-1]을 더해주는 값.

이것을 다 구하고 마지막에 생각해줄 필요없이 처음부터 나누고 시작하면 되는 문제였다.

def solution(money):
    n = len(money)
    ans = list()
    dp = [0]*n
    dp[0] = money[0]
    dp[1] = max(money[1],money[0])
    
    # [0]을 무조건 포함할 경우
    for i in range(2,n-1):
        dp[i] = max(dp[i-1], dp[i-2] + money[i])
    ans.append(dp[n-2])
    
    # [n-1]을 무조건 포함할 경우
    dp = [0]*n
    dp[0] = 0
    dp[1] = money[1]
    for i in range(2,n):
        dp[i] = max(dp[i-1], dp[i-2] + money[i])
    ans.append(dp[n-1])
    
    
    return max(ans)

 

번외 )

다른 사람의 풀이를 봤는데 진짜 개쩌는 코드가 있었다..

def solution(money):
    x1, y1, z1 = money[0], money[1], money[0]+money[2]
    x2, y2, z2 = 0, money[1], money[2]
    for i in money[3:]:
        x1, y1, z1 = y1, z1, max(x1, y1)+i
        x2, y2, z2 = y2, z2, max(x2, y2)+i
    return max(x1, y1, z2)

x1, y1, z1 의 경우는 첫번째 집([0]번째 값)을 선택했을 경우이고

x2, y2, z2 의 경우는 첫번째 집([0]번째 값)을 선택하지 않았을 경우이다.

 

for문에서는 하나씩 밀어가며 새로운 집 포함 시 금액을 계산해준다.

 

z1에서 더해주는 i의 경우 x1과 y1의 바로 인접한 값이 아니기 때문에 둘 중에 더 큰 값에 max를 해서 더해준다.

(예를들어 i가 3번째 값일경우 max계산에 이용되는 x1과 y1은 각각 0번째, 1번째의 dp값이다.

i가 4번째 값일 경우에는 x1과 y1이 1번째, 2번째의 dp가 된다.)

 

z1은 첫번째 집과 마지막 집이 모두 포함되기 때문에 max에서 제외해주고,

z2는 max(x2, y2) + i이기 때문에 x2,y2 < z2라 x2,y2가 max에서 제외된다.