2579 계단오르기

문제 링크

나의 풀이

i번 계단이 밟히는 방법 2가지

1. i - 1번 계단에서 1계단을 오른다
2. i - 2번 계단에서 2계단을 오른다

분할한 문제) 현재 밟은 계단 i는 어떻게 밟혔야 최대값을 갖는가? ⅰ) i - 1번째 계단에서 1계단 올라와서 밟힌다. ⅱ) i - 2번째 계단에서 2계단 올라와서 밟힌다. 캐싱할 부분이 2개로 나뉘어 저장해야 한다. 1계단 올라와서 기록, 2계단 올라와서 기록

0 1 2 3 v v v v v v v v

cache[0] -> 1계단 올라온 값을 캐싱한다. -> 무조건 2계단 올라야 한다. cache[1] -> 2계단 올라온 값을 캐싱한다. -> 2계단 오르거나 1계단 오르거나 2개로 나뉜다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] stairs = new int[n];
        int[][] cache = new int[3][n];

        for (int i = 0; i < n; i++)
            stairs[i] = Integer.parseInt(br.readLine());

        cache[0][0] = stairs[0];
        if (n >= 2)
            cache[0][1] = stairs[1] + stairs[0]; // 시작점은 포함되지 않는다.
        cache[1][0] = stairs[0];
        if (n >= 2)
            cache[1][1] = stairs[1];

        for (int i = 2; i < n; i++) {
            cache[0][i] = stairs[i] + cache[1][i - 1];
            cache[1][i] = stairs[i] + Integer.max(cache[1][i - 2], cache[0][i - 2]);
        }

        System.out.println(Integer.max(cache[0][n - 1], cache[1][n - 1]));
    }
}

다른 사람 풀이

cache[i]에 값에 최대 값을 넣는다. cache[i]에 들어갈 최대값 : (i - 2번 계단을 밟고 2계단을 오른값) vs (i - 3을 밟고 2 계단을 올라 i - 1을 밟은 뒤 1 계단 오른 값)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] stairs = new int[n + 1];
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++)
            stairs[i] = Integer.parseInt(br.readLine());

        dp[1] = stairs[1];
        if (n >= 2) {
            dp[2] = dp[1] + stairs[2];
        }

        for (int i = 3; i <= n; i++) {
            dp[i] = Integer.max(dp[i - 2], dp[i - 3] + stairs[i - 1]) + stairs[i];
        }

        System.out.println(dp[n]);
    }
}

결론

많은 경험을 통해 문제의 본질(점화식)을 꿰뚫어 보아야 한다.