백준 2579 계단 오르기 (파이썬)

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

첫번째 풀이 (재귀, 시간초과)

 

start: 시작 인덱스, 

seq: 연속 2개 선택하는 것 판단

result: 현재까지 선택한 계단의 합

 

def dfs(start, seq, result):
    global ans
    if seq > 2:
        return
    if start > N:
        return
    if start == 5:
        ans = max(ans, result)
        return
    if start + 1 < N:
        dfs(start + 1, seq+1, result+a[start+1])
    if start + 2 < N:
        dfs(start + 2, 1, result+a[start+2])

N = int(input())
a = []
ans = 0
for i in range(N):
    a.append(int(input().strip()))

dfs(0, 1, a[0])
dfs(1, 1, a[1])
print(ans)

시간초과로 틀렸습니다. 위 코드로 구현을 할 경우 O(2^(N)) 시간 복잡도를 가져 시간초과가 발생합니다.

피보나치 처럼 한번 dfs를 호출 할 때 마다 2번 호출 하므로 O(2^N) 입니다.

 

두번째 풀이 (DP, 통과)

dp[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때, 점수 합의 최댓값 (단, i번째 계단은 반드시 밟기)

 

N = int(input())
a = [0]
ans = 0

# dp[i][j] = 현재까지 j개의 계단을 연속해서 밟고, i번째 계단까지 올라섰을 때, 점수합의 최댓값
# (단, i 번째 계단은 반드시 밟기)
dp = [[0]*3 for i in range(N+1)]
for i in range(N):
    a.append(int(input().strip()))

if N == 1:
    print(a[1])
    exit(0)
elif N == 2:
    print(a[1] + a[2])
    exit(0)

dp[1][1] = a[1]
dp[2][1], dp[2][2] = a[2], a[1] + a[2]

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

print(max(dp[N]))

 

세번째 풀이(DP)

 

dp[i] = i번째 계단까지 올라섰을 때, 밟지 않은 계단 합의 최솟 값 (단 i 번째 계단은 반드시 밟지 않을 계단으로 선택)

total - min(dp[N-1], dp[N-2]) 

 

 

후기 

사실 이번이 처음 도전이 아니라서 재귀로도 안풀리면 답을 보려고 했습니다. 

그런데 정말로 안풀려서 답을 봤는데 생각보다 어렵더라구요 실버 3인데 저는 풀이법을 생각하지 못했습니다.

 

https://blog.encrypted.gg/974

[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍

BaaaaaaaarkingDog 님의 도움이 가장 컸던 것 같습니다.