[백준/BOJ] - 2579번 python 풀이 - DP

---

Key Point 

 

dp 문제를 보면 일단 dp 배열의 값에 어떤 값이 들어갈지 이에 대한 규칙을 찾아야 한다.

보통 1,2 와 같은 앞에 있는 번호들은 점화식에 적용되지 않는 경우가 많으므로 인지하고 진행.

 

d[0] = s[0]
d[1] = s[0] + s[1]
d[2] = max(s[0] + s[2], s[1] + s[2])
d[3] = max(d[0] + s[2] + s[3], d[1] + s[3]) 

# 2전 칸에서 1칸 이동 + 1칸 이동하여 해당 계단에 오는 경우도 있을 것이고

# 3전 칸에서 2칸 이동 + 1칸 이동하여 해당 계단에 오는 경우도 있다.

이 경우 중에 max값 도출.

 

 2156 포도주 문제와 다른 점은 해당 문제는 마지막 계단을 꼭 밟아야 한다는 조건 때문에 dp를 계산할 때 해당 idx의 계단을 밟는다고 가정하고 값을 구해야한다.

반면 포도주 문제는 해당 조건이 없으므로 바로 직전 포도주의 dp값을 그대로 넘겨받아도 문제가 없는 것이다.

 

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

https://taewogi.tistory.com/72

[백준/BOJ] - 2156번 python 풀이 - DP

---

n=int(input()) 
s=[int(input()) for _ in range(n)] 
dp=[0]*(n) 
if len(s)<=2: # 계단이 2개 이하일땐 더해서 출력
    print(sum(s))
else: # 계단이 3개 이상일 때
    dp[0]=s[0] # 첫째 계단
    dp[1]=s[0]+s[1] # 둘째 계단
    for i in range(2,n): # 3번째 계단 부터 dp 점화식 이용해서 최대값 구하기
        dp[i]=max(dp[i-3]+s[i-1]+s[i], dp[i-2]+s[i])
    print(dp[-1]) #배열 맨 마지막이 정답이므로