선택한 원소의 인접한 원소는 선택할 수 없을 때 원소 합을 최대로 선택하는 방법

7265번: Herbamedžiai (acmicpc.net)

 

 

배열에서 i번째 원소를 선택하면 i-1번째, i+1번째 원소는 선택할 수 없을때, 선택할 수 있는 원소의 최대 합을 구한다면

 

n이 최대 10만이라 O(N)에는 해결해줘야한다

 

$O(N^{2})$ 아니면 못할것 같지만 놀랍게도 O(N)에 되더라고

 

DP[i] = i번째 원소까지 봤을때 선택한 원소들의 최대합

 

만약 i번째 원소를 선택하지 않는다면?

 

dp[i] = dp[i-1]로 그대로 가져오면 된다

 

만약 i번째 원소를 선택한다면?

 

i-1번째 원소는 선택할 수 없으므로, dp[i-2]에다가 i번째 원소 선택 A[i]를 더해주면 된다

 

dp[i] = dp[i-2] + A[i]

 

여기서 둘 중 더 큰 값을 고르면 된다 dp[i] = max(dp[i-1], dp[i-2] + A[i])

 

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

 

근데 갑자기 생각난게 dp[i] = dp[i-2] + A[i]로 선택했다고 치면..?

 

i+1번째 나무는 선택할 수 없으니까 무조건 dp[i+1] = dp[i] 이건가?

 

i+1번째 나무를 선택해야할때...

 

dp[i+1] = dp[i-1] + A[i+1]

 

i+1번째 나무를 선택할 수 없을때..

 

dp[i+1] = dp[i]

 

그니까 i번째 나무가 선택되고 i+1번째 나무가 선택되는...경우가 있을 수 있는거 아니냐 이런 생각 했는데

 

i번째 나무가 선택되는 경우 dp[i] = dp[i-2] + A[i]

 

i+1번째 나무가 선택되는 경우 dp[i+1] = dp[i-1] + A[i+1]에서 dp[i]에서 A[i+1] 선택하면 문제되는데...

 

그게 아니니까 문제가 안되는거네 

 

내가 착각한듯

 

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

 

dp[i] = max(dp[i-1], dp[i-2] + A[i])는 i >= 2인 경우부터잖아

 

i = 0인 경우는 dp[0] = A[0]

 

i = 1인 경우는 dp[1] = max(dp[0], 0 + A[1])으로 초기화하면 적절하겠지

 

 

n = int(input())

A = list(map(int,input().split()))

dp = [0]*(n+1)
dp[0] = A[0]

if n > 1:
    
    dp[1] = max(A[0],A[1])

for i in range(2,n):
    
    dp[i] = max(dp[i-1], dp[i-2] + A[i])

print(dp[n-1])

 

 

 

의외로 비슷한 문제들을 풀었었네..;;

 

2156번: 포도주 시식 (acmicpc.net)

 

 

연속으로 놓여있는 3개의 원소는 선택할 수 없으면서 원소 합이 최대가 되도록 선택하는 문제

 

비슷하게 dp[i] = i번째 원소까지 봤을때 최대합

 

i번째 원소를 선택하지 않는다면, dp[i] = dp[i-1]

 

i번째 원소를 선택하고 i-1번째 원소는 선택하지 않는다면 dp[i] = dp[i-2] + A[i]

 

i번째 원소를 선택하고 i-1번째 원소도 선택한다면 dp[i] = dp[i-3] + A[i-1] + A[i]

 

from sys import stdin

n = int(stdin.readline())

dp = [0] * (n+1)

wine = [0]

for _ in range(n):
    
    a = int(stdin.readline())

    wine.append(a)

if n == 1:
    
    print(wine[1])

else:
    
    dp[1] = wine[1]
    
    dp[2] = wine[1]+wine[2]

    for i in range(3,n+1):
        
        dp[i] = max([dp[i-1], dp[i-2]+wine[i], dp[i-3]+wine[i-1]+wine[i]])

    print(dp[n])

 

 

 

2579번: 계단 오르기 (acmicpc.net)

 

 

한 계단 또는 두 계단을 오를 수 있는데 연속된 세 계단을 오를 수는 없다

 

dp[i] = i번째 계단에 오를때 얻을 수 있는 최대 점수

 

위와 비슷하게 연속된 세 계단을 밟을 수는 없으므로,

 

i번째 계단을 밟았다면 dp[i] = dp[i-2] + A[i]

 

한번에 두 계단씩 오를수도 있으므로 i-1번째 계단도 밟았다면 dp[i] = dp[i-3] + A[i-1] + A[i]

 

여기서 dp[i] = dp[i-1] + A[i]도 되는거 아니냐?

 

dp[i-1]이 ... + A[i-2] + A[i-1]일 수 있기 때문에 이런 경우 세 계단 연속으로 밟을 수 있어서 안됨

 

dp[i] = dp[i-1]로 i번째 계단을 꼭 밟아야하냐?

 

마지막 도착 계단을 밟아야하므로 i번째 계단을 꼭 밟아야함

 

근데 마지막 도착 계단을 밟는거랑 상관없이 i번째 계단에 오른다면 그 계단의 점수는 가져가는게 자연스러운거 아녀?

 

흠..

 

from sys import stdin

n = int(stdin.readline())

dp = [0] * (n+1)

stairs = [0]

for _ in range(n):
    
    a = int(stdin.readline())

    stairs.append(a)

if n == 1:
    
    print(stairs[1])

else:
    
    dp[1] = stairs[1]

    dp[2] = max(stairs[1] + stairs[2], stairs[2])

    for i in range(3,n+1):

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

    print(dp[n])