백준 2579 — 계단 오르기: 연속해서 밟은 계단 수를 상태로

백준 2579 문제 보기

문제에서 지켜야 할 규칙

한 번에 한 계단 또는 두 계단씩 오를 수 있다. 연속된 세 계단을 모두 밟을 수 없으며, 마지막 계단은 반드시 밟아야 한다. 시작점은 계단 수에 포함하지 않는다.

1. 테이블 정의하기

D[i][j]는 i번째 계단을 반드시 밟고, 연속해서 j개의 계단을 밟은 상태에서의 점수 합 최댓값이다. 여기서 j는 1 또는 2다.

지금까지 몇 개를 연속으로 밟았는지에 따라 다음 선택이 달라진다. 따라서 계단마다 점수 하나만 남기지 않고 두 상태를 따로 저장한다.

2. 점화식 찾기

D[i][1] = max(D[i - 2][1], D[i - 2][2]) + score[i]
D[i][2] = D[i - 1][1] + score[i]

• 연속 1개 상태: i-1번째 계단을 건너뛰고 i-2번째에서 온다. 이전의 연속 횟수는 1 또는 2 모두 가능하다.
• 연속 2개 상태: i-1번째 계단에서 온다. 세 계단 연속을 피하려면 이전 상태는 반드시 연속 1개여야 한다.

둘 다 마지막 계단을 밟은 상태이므로 답은 Math.max(D[N][1], D[N][2])다.

3. 초기값 정의하기

D[1][1] = score[1]
D[1][2] = 불가능
D[2][1] = score[2]
D[2][2] = score[1] + score[2]

시작점에서 두 번째 계단으로 바로 오를 수도 있다. 불가능한 상태는 최댓값 비교에서 선택되지 않도록 -Infinity로 둔다. 계단이 하나인 경우에는 두 번째 행을 만들거나 읽지 않는다.

4. 코드 구현하기

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [N, ...stairs] = fs.readFileSync(filePath, 'utf-8').trim().split(/\s+/).map(Number);
 
function solution() {
    const D = Array.from({ length: N + 1 }, () => Array(3).fill(-Infinity));
    D[1][1] = stairs[0];
    if (N >= 2) {
        D[2][1] = stairs[1];
        D[2][2] = stairs[0] + stairs[1];
    }
    for (let i = 3; i <= N; i++) {
        D[i][1] = Math.max(D[i - 2][1], D[i - 2][2]) + stairs[i - 1];
        D[i][2] = D[i - 1][1] + stairs[i - 1];
    }
    console.log(Math.max(D[N][1], D[N][2]));
}
 
solution();

왜 연속 횟수별로 나눠야 할까?

원래 메모의 코드는 계단마다 [연속 횟수, 최대 점수] 하나만 저장하고 다음 선택을 했다. 하지만 그 상태가 다음 계단을 밟을 수 없다면, 버렸던 다른 경로가 정답일 수 있다.

예를 들어 점수가 [1, 2, 1]이면 두 번째 계단까지의 최대 점수는 첫째·둘째를 밟은 3이다. 여기서 연속 횟수 2인 경로만 남기면 셋째로 이어갈 수 없어 첫째·셋째의 2를 선택하게 된다. 실제 최적 경로는 둘째·셋째를 밟는 3이다.

앞으로 가능한 선택이 다른 경로는, 현재 점수가 작더라도 별도 상태로 남겨야 한다.

확인할 경계 사례는 계단 1개, 계단 2개, 위 반례다. 원문에 빠졌던 solution() 호출도 코드 끝에 추가했다.

복잡도

시간 O(N), DP 테이블 공간 O(N). 계단마다 두 가지 유효 상태만 계산한다.

참고 자료

바킹독의 실전 알고리즘 0x10강 — 다이나믹 프로그래밍을 학습하며 작성한 메모를 바탕으로 정리했다. 포함된 이미지는 원본 학습 메모의 캡처다.