[BOJ] 2156, 2579

문제 2156
문제 2579
.. 점화식을 잘 세워야 한다..
DP 점화식 연습 ..!!! 손으로 풀어보는게 좋을듯

others

2156

출처 - 민지

'''
n번째 잔을 마셨을 때
1. n-1잔을 마셨으면 n-2잔은 불가능
2. n-1잔을 안 마셨으면 n-2잔은 가능
3. 현재 잔을 안마시는 경우
점화식
1. dp(n)=dp(n-3)+glass(n-2)+glass(n)
2. dp(n)=dp(n-2)+glass(n)
3. dp(n-1)
이 세 경우 중 가장 큰 값을 저장
'''
import sys

n=int(input())
glass=[]
for i in range(n) :
    glass.append(int(sys.stdin.readline()))

dp=[0]*n

dp[0]=glass[0]
if n>1 :
    dp[1]=glass[0]+glass[1]

if n>2 :
    dp[2]=max(glass[0]+glass[2], glass[1]+glass[2], dp[1])

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

print(dp[n-1])

2579

출처

n = int(input())
s = [0 for i in range(301)]
dp = [0 for i in range(301)]
for i in range(n):
    s[i] = int(input())
dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])
for i in range(3, n):
    dp[i] = max(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i])
print(dp[n - 1])

dp리스트의 첫번째에는 당연히 s리스트 첫번째 점수가 들어가고,
dp[1]에는 s[0] + s[1] 즉, 첫번째 점수와 두번째 점수를 합한 값을 넣어준다.
dp[2]에는 첫번째 계단을 밟고 두 계단을 올랐을때 합과 두번째계단을 밟고 한 계단을 올랐을때 합중 큰 값을 넣어준다.
마지막 계단은 꼭 밟아야 하므로
1. 마지막 계단의 전 계단을 밟은 경우
2. 마지막 계단의 전 계단을 밟지 않은 경우가 있다.
그러므로 dp[i]에는 dp[i - 3] + s[i] + s[i - 1]와 dp[i - 2] + s[i] 이 들어갈 수 있다.
이 두값중에서 큰 값을 넣어준다.