백준 2579 계단 오르기

백준 2579

오늘은 백준 계단 오르기 문제를 풀었다. 어제부터 본격적으로 DP 파트를 풀기 시작했는데 참 재밌다.

문제는 쉬운거 같은데도 30분이나 걸렸다. 처음에 1차원 배열로만 해결을 하려다가 생각을 다시 해 2차원으로 도전했고, 성공했다.


핵심은 한 계단 마다 이전 칸을 밟은 경우와 밟지 않은 경우에 대한 값을 모두 저장하고 있는 것이다.


코드는 다음과 같다!

import static java.lang.Math.max;

import java.util.Scanner;

public class Boj_2579 {

    public static void main(String[] args) {
        int stair[] = new int[303];
        int table[][] = new int[303][2];
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        for (int i = 1; i <= n; i++) {
            int input = Integer.parseInt(scanner.nextLine());
            stair[i] = input;
        }
        table[1][0] = stair[1];
        table[1][1] = stair[1];
        table[2][0] = table[1][0] + stair[2];
        table[2][1] = stair[2];
        for (int i = 3; i <= n; i++) {
            table[i][0] = table[i - 1][1] + stair[i];
            table[i][1] = max(table[i - 2][0], table[i - 2][1]) + stair[i];
        }
        System.out.println(max(table[n][0], table[n][1]));
    }
}

보면 table[][] 이 2차원으로 설정되어있고, table[i][0] 의 경우는 i-1 칸에서 바로 밟는 경우의 값을, table[i][1]의 경우에는
i-2 칸에서 바로 넘어온 경우에 대한 값을 저장하고 있다.


이후 출력할 때는 table[n][0], table[n][1] 중 더 큰 값을 찍어주면 되겠지!