[백준] 2578 계단 오르기 (파이썬 Python)

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

2579번: 계단 오르기

문제 설명

---

풀이 과정

• 나의 풀이

① 이 문제를 풀며 느낀건... DP문제 첫 문제로 풀었던 '1463 1로 만들기'문제유형이 이렇게 중요할 줄이야! 이다..

② 일단 이 문제의 중요한 조건은 연속된 세 개의 계단을 밟아서는 안되고, 마지막 계단은 무조건 밟아야하며 계단을 한번에 한 계단 혹은 두 계씩 오를 수 있다는 것이다.

③ 마지막을 무조건 밟아야하니... DP식을 작성할 때 상향식으로 작성해야겠다는 생각이 들었다.

④ 아이디어 열기

 예를 들어 계단의 수가 10개라면 ... (array리스트는 문제에서 입력받은 계단의 점수값리스트)

dp[1] = array[1]

dp[2] = array[1]+array[2]

dp[3] = max(array[1]+array[3],array[2]+array[3])

dp[4] = max(dp[1]+array[3]+array[4],dp[2]+array[4])

dp[5] = max(dp[2]+array[4]+array[5],dp[3]+array[5])

....

 이다. 왜냐하면 dp[5]를 계산할 때 5번째 칸의 계단입장에서 생각해보면... 5번째 칸의 계단을 무조건 밟는다는 가정하에 2번째 칸의 계단에서 4번째,5번째 칸의 계단을 밟으러 올 수도 있고, 3번째 칸에서 5번째 칸으로 바로 밟으러 오는 경우가 있을 수도 있다.

 이를 점화식으로 표현하면 다음과 같다.

dp[n] = max(dp[n-3]+array[n-1]+array[n],dp[n-2]+array[n]) (단, n>=4)

 이를 코드로 구현하면 다음과 같다. 

# 2579 계단 오르기
import sys
input = sys.stdin.readline

N = int(input())
dp = [0]*(N+3)
arr = [0]*(N+3)
for k in range(1,N+1):
    arr[k] = int(input())

dp [1] = arr[1]
dp [2] = arr[1] + arr[2]
dp [3] = max(arr[1] + arr[3] ,arr[2] + arr[3])

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

print(dp[N])

 시간초과가 뜨길래 sys.stdin.readline을 오랜만에 사용했다-!

---

후기

  1로 만들기 유형을 생각하면서 문제를 푸니깐 어느정도 쉽게 해결된 것 같다..!!!