백준 2579 파이썬 | 계단 오르기

코드

n = int(input())
s = [0 for i in range(301)]
dp = [0 for i in range(301)]
for i in range(n):
    s[i] = int(input())
dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])
for i in range(3, n):
    dp[i] = max(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i])
print(dp[n - 1])

출처: https://pacific-ocean.tistory.com/149

설명

오랫동안 고민했음에도 결국 풀어내지 못한 문제다. 계단 3칸을 연속으로 이동할 수 없기 때문에 그러면 한 칸을 움직일 때마다 연속으로 몇 칸 움직였는지 변수에 저장해야 하나 싶었다. 아니면 그리디 알고리즘으로 최댓값을 보고 올라야하나 싶었지만 조금만 생각해 보면 아니었다. 아니면 도착 지점에서 시작해서 시작지점으로 내려가도록 알고리즘을 짜면 될까 싶었는데 그냥 어떻게 하나 똑같았다. 이런저런 생각이 모두 겹쳐서 아주 복잡한 알고리즘이 만들어졌고 그것도 사실 틀렸다.

 

알고 보니 관점의 전환이 필요한 문제다. 중요한 것은 앞으로 어떻게 나아가야 하는지가 아니라 내가 한 칸 전 계단에서 올라왔는지 두 칸 전 계단에서 올라왔는지의 여부이다. 동적프로그래밍을 이용하여 n번째 계단에 올라왔을 때의 최댓값을 저장하면 된다. 한 칸 전에서 올라왔다면 다시 그 전에는 두 칸 전에서 올라온 것이기 때문에 dp[i-1] + dp[i-3]을 해주고 여기서 내가 있는 칸의 값인 s[i]까지 더해준다. 두 칸 전에서 올라왔다면 다시 그 전에 몇 칸 전에서 올라온 것인지는 중요하지 않기 때문에 두 칸 전일 때의 최댓값과 내가 있는 칸의 값을 더해 dp[i-2] + s[i] 가 된다. 한 칸 전에서 올라왔을 때의 최댓값과 두 칸 전에서 올라왔을 때의 최댓값중 큰 값을 채택하면 그게 n 번째 칸에 올라왔을 때의 최댓값이 된다. 그렇게 dp 리스트를 채워 나가면 풀리는 것이다.

 

나름 발상의 전환을 한답시고 했었음에도 '내가 몇 칸 전에 올라왔는가' 와 같은 생각은 나지 않았다. 이런저런 경험이 쌓이다 보면 나도 문제 풀 때 핵심적인 발상의 전환을 할 수 있겠지..?

 

메모리: 29200 KB

시간: 92 ms

문제

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

2579번: 계단 오르기