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

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

2579번: 계단 오르기

 

작성코드

 

 

 

해설

 

문제에서 룰은 총 세가지이다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

 

이를 계산하기 위해 모든 과정을 탐색 알고리즘인 DFS로 푼다면 엄청난 시간이 걸리게 된다.

이를 대신하여 DP 방식으로 구현을 한다.

DP는 이전 계산 결과를 메모리에 저장하여 활용하는 풀이 방법이다.

 

마지막 계단을 밟았을 때 바로 이전 계단을 밟았다면 전전 계단은 밟을 수 없으며

바로 이전 계단을 밟지 않았다면 전전 계단을 밟아야 마지막 계단에 도착이 가능할 것이다.

 

두 경우의 수 중에서 어떤 경우든

그 계단 또한 동일한 경우의 수가 발생하게 될 것이다.

이렇게 반복되는 형태를 코드로 구현하면

 

 

이와 같은 형태가 된다.

 

 

※ 런타임 에러

 

문제가 발생한 원인

맨 처음 풀 때 자꾸 런타임 에러 문제가 발생하게 되었다. 그 이유는 최대한 메모리를 줄이기 위해서 계단의 수만큼 배열을 만들어 주었는데 예시로 주는 계단들에는 문제없이 작동하나

N = 1 준다면 맨 처음 명시한 dp[2]가 생성되지 않고 for문에서 step[2], step[3], dp[2], dp[3] 또한 만들 수 없어 오류가 발생한다.

 

 

이러한 문제를 방지하기 위해 문제에 주어진 입력 계단 한계인 300을 범위로 잡아주면 된다.