원형 배열에서의 다이나믹 프로그래밍 기본

https://school.programmers.co.kr/learn/courses/30/lessons/12971?language=python3

프로그래머스

 

 

원형으로 연결된 배열에서, i번째 원소를 선택했을때, 서로 인접한 i-1번, i+1번 원소를 선택할 수 없다.

 

이런 경우 n개의 원소 중 적절히 선택하여 최댓값을 구하는 문제

 

원형으로 연결되어 있기 때문에, 1번 원소를 선택하는 경우 2번 원소와 n번 원소를 선택할 수 없다

 

마찬가지로 n번 원소를 선택하는 경우 1번 원소와 n-1번 원소를 선택할 수 없다.

 

------------------------------------------------------------------------------------------------------------------------------------------

 

단순하게 일렬로 배열되어 있다고 가정할때, 문제를 어떻게 해결할 수 있을까?

 

i번째 원소까지 봤을때 원소 합들의 최댓값을 dp[i]라고 정의한다면

 

i번째 원소를 선택하지 않고 넘어가는 경우 dp[i-1]

 

i번째 원소를 선택한다면, i-1번째 원소는 선택하지 말아야하므로 dp[i-2] + A[i]

 

둘 중 최댓값을 선택해야하므로 dp[i] = max(dp[i-1], dp[i-2] + A[i])

 

그런데 원형으로 배열된 경우는 0번 원소를 선택하는 경우와 0번 원소를 선택하지 않는 경우 2가지로 나눠서

 

dp1은 0번 원소를 선택하는 경우

 

dp1[0] = A[0]로 초기화

 

#0번 원소를 선택하는 경우
dp = [0]*n

dp[0] = sticker[0]

for i in range(1,n-1):

    if i >= 2:

        dp[i] = max(dp[i-1],dp[i-2] + sticker[i])

    else:

        dp[i] = dp[i-1]

#0번을 선택했으면 n-1번 원소는 선택할 수 없으므로
dp[n-1] = dp[n-2]

 

 

dp2는 0번 원소를 선택하지 않는 경우, dp2[0] = 0으로 초기화

 

#0번 원소를 선택하지 않는 경우
dp = [0]*n

dp[1] = sticker[1]

for i in range(2,n):

    dp[i] = max(dp[i-1], dp[i-2] + sticker[i])

v2 = dp[n-1]

 

 

2가지 경우중 더 큰 값을 선택하면 된다

 

이때 n = 1인 경우 인덱스 에러가 나는데 예외 처리 하면 되겠다

 

n = 1인 경우는 해당 원소를 선택하는게 무조건 최대

 

def solution(sticker):
    answer = 0
    
    n = len(sticker)
    
    #n = 1인 경우 해당 원소를 선택하는게 무조건 최대
    if n == 1:
        
        return sticker[0]
    
    #0번 원소를 선택하는 경우
    dp1 = [0]*n
    
    dp1[0] = sticker[0]

    for i in range(1,n-1):
        
        if i >= 2:
            
            dp1[i] = max(dp1[i-1],dp1[i-2] + sticker[i])
        
        else:
            
            dp1[i] = dp1[i-1]
    
    dp1[n-1] = dp1[n-2]
    
    v1 = dp1[n-1]
    
    #0번 원소를 선택하지 않는 경우
    dp2 = [0]*n
    
    dp2[1] = sticker[1]
    
    for i in range(2,n):
            
        dp2[i] = max(dp2[i-1], dp2[i-2] + sticker[i])
        
    v2 = dp2[n-1]
    
    return max(v1,v2)