[백준] 파이썬 2579번 계단 오르기

- 문제:

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

2579번: 계단 오르기

 

- 코드: 

(01.27) 처음에 dp 방식으로 풀지 않고 구현하려하다 봉변당했다.., DP 문제 유형 잘 익히자. 이 글도 한번 날라가서 다시쓰는중ㅠㅠ 화이팅..

조건 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

을 참고하여 점화식 발굴

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

 

dp[0] 일 경우는 1칸을 갔을 경우이다.

--> 1칸을 가기위해서는 단 하나의 경우 밖에없다.

dp[1] 일 경우는 2칸을 갔을 경우이다.

--> 2칸을 가기위해서는 1칸+1칸 갔을 경우와 한번에 2칸을 갔을 경우로 나눌수 있다. 이 두경우 중 최대값을 저장한다.

dp[2] 일 경우는 3칸을 갔을 경우이다.

--> 3칸을 가기위해서는 1칸+2칸 갔을 경우와 2칸+1칸 갔을 경우로 나눌수 있다. 이 두경우 중 최대값을 저장한다.

 

n = int(input())
arr = []

for _ in range(n):
    arr.append(int(input()))
    
dp[0] = arr[0]
dp[1] = max(arr[0] + arr[1], arr[1]) # 두칸 올라갔을때 최대
dp[2] = max(arr[1]+arr[2],arr[0] + arr[2])  # 세칸 올라갔을때 최대

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

print(dp[n-1])