[백준]2579 계단 오르기(Python)

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

2579번: 계단 오르기

 

문제 접근

 

프로그래머스의 던전 문제처럼 DFS를 사용해서 풀 수 있지 않을까 생각했다. 

하지만 조건이 연속해서 3개의 계단을 밟을 수 없고, 무조건 마지막 계단을 밟아야 했기에 이를 조건으로 추가하고 싶었다.

계단은 앞으로 올라가는 것뿐이라서 던전과 다르게 방문여부를 체크할 필요가 없었다. 

 

코드

import sys
input = sys.stdin.readline

N = int(input())
stairs = []
answer = 0  # 최댓값을 저장할 변수

def DFS(stairs, idx, total, cnt): # idx는 현재 계단의 위치, cnt는 연속으로 밟은 계단의 수 => check 필요x
    global answer

    if idx >= N:
        return

    if idx == N-1:
        answer = max(answer, total)
        return

    # 계단 하나를 오르는 경우에는 연속된 계단이 2개 이하
    if (cnt < 2 and idx+1 < N) :
        DFS(stairs, idx+1, total+stairs[idx+1], cnt+1)

    # 계단 두개를 오르는 경우 cnt를 0으로 초기화
    if idx + 2 < N:
        DFS(stairs, idx+2, total+stairs[idx+2], 1)


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


DFS(stairs, 0, stairs[0], 1) # 첫 번째 계단에서 시작
if N > 1:
    DFS(stairs, 1, stairs[1], 1)

print(answer)

 

++DP코드

import sys
input = sys.stdin.readline

N = int(input())

# 최대 300개의 계단이 주어질 수 있으므로 300으로 초기화
stairs = [0 for _ in range(300)]

# 각 계단까지 도달하는 데 얻을 수 있는 최대 점수를 저장할 DP 테이블. 계단의 수와 동일하게 300으로 초기화
dp = [0 for _ in range(300)]

# 입력 받은 계단의 점수를 stairs 리스트에 저장
for i in range(N):
    stairs[i] = int(input())

# 첫 번째 계단까지 도달하는 데 얻을 수 있는 최대 점수는 첫 번째 계단의 점수
dp[0] = stairs[0]

# 두 번째 계단까지 도달하는 데 얻을 수 있는 최대 점수는 첫 번째 계단과 두 번째 계단의 점수의 합
if N > 1:
    dp[1] = stairs[0] + stairs[1]

# 세 번째 계단까지 도달하는 데 얻을 수 있는 최대 점수는 두 가지 경우 중 최대값
# 1) 첫 번째 계단을 밟고 세 번째 계단으로 이동
# 2) 두 번째 계단을 밟고 세 번째 계단으로 이동
if N > 2:
    dp[2] = max(stairs[1] + stairs[2], stairs[0] + stairs[2])

# 네 번째 계단부터는 두 가지 경우 중 최대값을 DP 테이블에 저장:
# 1) i-2번째 계단을 밟고 i번째 계단으로 이동(i-2 => i)
# 2) i-3번째 계단을 밟고 i-1번째 계단을 밟고 i번째 계단으로 이동(i-3 => i-1 => i)
for i in range(3, N):
    dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

# 마지막 계단까지 도달하는 데 얻을 수 있는 최대 점수를 출력 => 마지막 계단 무조건 밟기!!
print(dp[N-1])

 

회고

 

DFS로 푼 코드는 시간초과가 발생했다. 

DFS는 가능한 모든 경로를 탐색하기 때문에 입력 크기가 커지면 처리 시간 증가 => O(2^N) 오르거나 오르지X

 

DP의 경우 문제를 더 작은 부분 문제로 나누고, 이 부분 문제의 해를 저장하여 재사용함으로써 효율적으로 문제를 해결 => O(N)

 

추가로 만약 밟는 계단의 수가 정해져 있을 때의 최대 점수 구하는 것도 생각해보자!