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

하루에 적어도 한 문제는 풀고 싶은데, 요즘 너무 바빠서 블로그에 풀이를 남기는 건 일주일에 한 번 꼴로 하게 될 것 같다.. 빨리 취업해서 역량을 펼치고 싶다.

 

DP - Dynamic Programming

---

백준의 카테고리 중 "분류 별 풀어보기"를 들어가보면 가장 많은 문제를 차지하고 있는 문제 유형이다.

동적 프로그래밍이라는 알고리즘? 풀이방법?

나는 알고리즘이라는 말 보단 풀이 방법이라는 단어가 더 어울리는 것 같다.

정의는 위키백과에 찾아보면 되고, 내가 생각하는 동적 프로그래밍을 재 정의해보면 "재활용"이라고 생각한다.

 

구현하는 건 어려울게 하나도 없다. 정말 이전의 값을 재활용해서 불필요한 반복을 없애고, 그만큼 시간 복잡도를 줄이도록 구현하면 된다.

 

문제

---

풀이를 위한 조건 간단하게 정리

1. 계단은 한 칸 혹은 두 칸씩 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. => 두 번 "한" 칸씩 올랐다면 무조건 그다음은 "두" 칸을 올라감.

3. 마지막 도착 계단은 반드시 밟아야 한다. => 뒤에서 시작하면서 풀이를 시작하면 된다.

 

풀이

---

먼저 필요한 모듈 및 변수를 선언한다.

DP에 사용될 배열과 입력을 받을 배열을 선언한다.

import sys
input = sys.stdin.readline
arr = []
dp = []

 

문제를 파이썬으로 풀 때 배열로 입력을 받아야 한다면 append 함수를 쓰는 게 제일 효율적인 거 같다.

C와 다르게 python에서는 가장 뒤에 원소를 추가하는 게 시간 복잡도가 O(1)이기 때문이다.

 

l = int(input())
for _ in range(l):
    arr.append(int(input()))

문제에 필요한 입력을 받아서 적절하게 변수에 저장해둔다.

 

이제 정답을 구해보자

문제에서 필요한 조건 중 3번을 만족시키기 위해 맨 마지막 계단(= END)이 밟혀있다고 가정해보자.

그렇다면 그 전의 계단은 "END - 1" 계단이거나, 맨 마지막 "END - 2" 계단 일 것이다.

 

두 개의 경우에 문제 2번 조건을 적용시켜보자

밟은 계단이 "END - 1"일 경우 반드시 "END - 2" 계단을 밟으면 안 된다. - case_A

밟은 계단이 "END - 2"일 경우 그 전 계단은 신경 쓰지 않는다. - case_B

 

내가 만약 다이나믹 프로그래밍을 통해 배열 "dp"에 앞에서부터 밟아온 계단 중 가장 최대의 값을 저장해 왔다면 다음 수식처럼 정리할 수 있다. ex) dp[4] => 네 번째 계단까지 계산했을 때 가장 큰 경우 값을 저장

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

수식을 한국말로 해설해보면

"i번 째 계단까지의 최대 가중치 합" = "case_B : i - 2번째 계단까지의 최대 가중치 합 + 현재 계단의 가중 치"와 "case_A : i- 3번째 계단까지의 최대 가중치 합 + i - 1번째 계단의 가중치 + 현재 계단의 가중 치" 중 더 큰 값

수식을 이렇게 정리해 보니 어떤 값이 선택되든 현재 계단의 가중 치가 포함되어있기 때문에 3번 조건을 만족하게 되면서 풀이 완성되었다.

 

아래는 정답 코드이다.

import sys
input = sys.stdin.readline
arr = []
dp = []

l = int(input())
for _ in range(l):
    arr.append(int(input()))

dp.append(arr[0])
dp.append(max(arr[0]+arr[1],arr[1]))
dp.append(max(arr[0]+arr[2],arr[1]+arr[2]))
for i in range(3,l):
    dp.append(max(dp[i-2] + arr[i] , dp[i-3] + arr[i] + arr[i - 1]))

print(dp.pop())

 

처음에 for문 밖에서 dp에 값을 넣어주는 이유는 수식에 i - 3이 들어가서 인덱스 범위를 지켜주기 위해서 이다.

세 번째 칸 까지만 하드코딩하면 된다!

 

---

혹시나 해서 단순 재귀로 풀어봤는데 역시나 시간 초과다 ㅋㅋ

동적 프로그래밍의 강력함을 다시 한번 느끼며 오늘 공부 끝!