[백준 2579번] 계단 오르기 (python/파이썬)

DFS로 풀었다가 실패하고 DP로 성공

실버 3 절대아님

 

🌼 문제 링크

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

2579번: 계단 오르기

• 티어:  실버 III
• 분류: 다이나믹 프로그래밍

 

 

❗ TRIAL 1.

코드

import sys
input = sys.stdin.readline

def dfs(stairs, val, ctr):
    if not stairs:
        return val
    next_val = stairs.pop()
    if ctr != 2:
        dfs1 = dfs(stairs, val+next_val, ctr+1)
        dfs0 = dfs(stairs, val, 0)
        stairs.append(next_val)
        return max(dfs1, dfs0)
    else:
        dfs0 = dfs(stairs, val, 0)
        stairs.append(next_val)
        return dfs0

N = int(input())
stairs = []
for _ in range(N):
    stairs.append(int(input()))

val = stairs.pop()
print(dfs(stairs, val, 1))

 

코드 설명

 

- 연속으로 몇개의 계단을 밟았는지를 세는 ctr을 dfs에 함께 전달함

- 만약 ctr이 2이면, 다음 계단은 밟지 않음. ctr은 0으로 초기화

- ctr이 2가 아니면, 다음 계단을 밟는 경우와 밟지 않는 경우 중 큰 값을 이용. 다음 계단을 밟는 경우 ctr에 1 추가

 

틀린 원인

 

시간초과. DFS로 풀면 거의 binary tree와 비슷하기 때문에 O(N^2) 시간이 걸린다. (구현은 제일 간단)

 

 

❗ TRIAL 2.

코드

import sys
input = sys.stdin.readline

N = int(input())
stairs = []
for _ in range(N):
    stairs.append(int(input()))

d0 = [0] * N
d1 = [0] * N
dmax = [0] * N

d0[0], d1[0] = stairs[0], stairs[0]
d0[1], d1[1] = stairs[1], stairs[0]+stairs[1]
dmax[0] = max(d0[0], d1[0])
dmax[1] = max(d0[1], d1[1])

for i in range(2, N):
    d0[i] = dmax[i-2] + stairs[i]
    d1[i] = d0[i-1] + stairs[i]
    dmax[i] = max(d0[i], d1[i])

print(dmax[N-1])

 

수정한 부분

 

- DFS bottom-up 방식으로 수정

- 이전 계단을 밟은 경우인 d0, 이전 계단을 밟지 않은 경우인 d1, 두 경우의 최댓값인 dmax 세 개의 array를 계산함

- d0을 계산할때는 두칸 전의 dmax값에 현재 계단 값을 더함

- d1을 계산할때는 한칸 전의 d0값에 현재 계단 값을 더함

- d0과 d1을 계산한 후 dmax 값을 계산

 

틀린 원인

 

Runtime error. 계단이 하나인 경우를 고려 못함

 

💡 Solution

코드

import sys
input = sys.stdin.readline

N = int(input())
stairs = [0]
for _ in range(N):
    stairs.append(int(input()))

d0 = [0] * (N+1)
d1 = [0] * (N+1)
dmax = [0] * (N+1)

d0[1], d1[1] = stairs[1], stairs[1]
dmax[1] = max(d0[1], d1[1])

for i in range(2, N+1):
    d0[i] = dmax[i-2] + stairs[i]
    d1[i] = d0[i-1] + stairs[i]
    dmax[i] = max(d0[i], d1[i])

print(dmax[N])

 

코드 설명

• DFS bottom-up
• 이전 계단을 밟은 경우인 d0, 이전 계단을 밟지 않은 경우인 d1, 두 경우의 최댓값인 dmax 세 개의 array를 계산함
• d0을 계산할때는 두칸 전의 dmax값에 현재 계단 값을 더함
• d1을 계산할때는 한칸 전의 d0값에 현재 계단 값을 더함
• d0과 d1을 계산한 후 dmax 값을 계산
• 시작위치를 0으로 잡음

• •