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

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

2579번: 계단 오르기

---

풀이과정

①문제 들여다보기

dp 문제임은 자명하고, dp테이블을 만들어서 for문을 통해서 답을 도출하는 것임에 분명하다.

계단을 타는 조건은 세 가지인데

1. 한 번에 한 계단 또는 두 계단씩 오를 수 있음
2. 연속된 세 계단은 오를 수 없음
3. 마지막 도착 계단은 무조건 밟아야함

②아이디어 펼치기

1번 조건은 for문으로 해결할 수 있다. 

3번 조건은 계단순서를 reverse해서 미리 한 칸을 밟아놓은 상태로 시작하면 된다.

그러나 2번조건이 해결하기 어렵다고 느꼈다.

 

개판인 코드

무작정 대충 짜봤는데 굉장히 엉망이 되었다. 일단 index도 문제고 걍 전체적으로 문제이기 때문에 다른 방법을 탐색해야하나 고민하기 시작했다.

 

그러다 지민 굉장히 당황스러운 사실을 깨달았다..

 

그냥 for문을 돌려서 i번째 칸까지 오는데 제일 많이 점수를 딸 수 있게 하면 매번 계산하다 보면 결국 N일 때 최대인 값을 구하게 된다는 사실이다. 그렇게하면 굳이 reverse를 해서 구할 필요가 없고 3칸 3칸 묶어서 계산할 수 있게 되어서 2번 문제도 해결이 되는 것이다. 우욱...

 

index를 편하게 보기 위해서 0번째 인덱스에 미리 0을 채워놓고 짜보도록했다.

이 문제는 "마지막 칸까지 어떻게 갈지"에 포인트를 둬야 풀린다. 마지막 칸까지 가는 방법은

1. 한 칸 그냥 올라가는 방법
2. 한 칸 띄워서 올라가는 방법

이 있다. 이 방법들을 표현하면,

이렇게 두가지가 있다.

1번 방법의 경우 

왼쪽과 같이 올라가면 안된다. 무조건 오른쪽만 가야하기에, 코드가 아래와 같이 된다.

dp[i-3] + stair[i-1] + stair[i]

 

2번 방법의 경우

앞이 어쨌든 간에 한 칸을 뛰기 때문에 아무 상관이 없다. 그래서 코드는 아래와 같다.

dp[i-2] + stair[i]

 

③최종 코드

N = int(input())
stair = [0]
for _ in range(N):
    stair.append(int(input()))

dp = [0]*(N+1)

if N == 1:
    print(stair[1])
else:
    dp[1] = stair[1]
    dp[2] = stair[1] + stair[2]

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

---

후기

이 문제를 보고, 해결하고자 하는 부분 문제들의 중복 여부를 판단해야 함을 몸소 깨닫게 되었다. 

가령, 12번째 계단까지 올라야한다고 가정했을 때, 10번째 계단이나 11번째 계단에서 이미 최적의 조건이 계산되어 있어야한다. 그리고 10번째나 11번째 계단은 그 전 과정을 통해서 또 최적의 조건이 계산되어있어야하며 이것을 연쇄적으로 타고 내려가면 저 밑까지 내려간다. 그렇다는 것은 각 층마다 어떻게든 중복되는 연산이 있다는 소리고 이것을 알게되면 위에서 내가 했던 방식처럼 가짓수를 세고, 그 연산 방법만 고안한다면 코드가 짜여진다는 것이다.

배울게 나름 있었던 문제였던 것 같다.