[백준] 계단 오르기

참고 : www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

- dp 문제

- 테이블 정의를 어떻게 하느냐에 따라 다르게 풀이 될 수 있는 점이 흥미로웠다.

- dp[i] : i 번째 계단을 밟지 않는 경우의 수의 최소 값 (i-1은 반드시 선택, i-2 or i-3 번째 중에 값을 선택하는 것)

 

import java.util.Scanner;

public class Solution {
	// 밟지 않는 경우의 수 체크
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int sum = 0;
        int n = sc.nextInt();
        int[] s = new int[305];
        for(int i = 1; i<=n; i++) {
            s[i] = sc.nextInt();
            sum += s[i];
        }
        if(n <= 2) {
            System.out.println(sum);
            return;
        }
        int[] dp = new int[305];
        dp[1] = s[1];
        dp[2] = s[2];
        dp[3] = s[3];
        for(int i=4; i<=n-1; i++) {
            dp[i] = Math.min(dp[i-2], dp[i-3]) + s[i];
        }
        System.out.println(sum - Math.min(dp[n-1], dp[n-2]));
    }
    // 밟는 경우의 수를 체크
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[] s = new int[n+5];
//        for(int i = 1; i<=n; i++) {
//            s[i] = sc.nextInt();
//        }
//        int[][] dp = new int[305][3];
//        dp[1][1] = s[1];
//        dp[1][2] = 0;
//        dp[2][1] = s[2];
//        dp[2][2] = s[1] + s[2];
//        for(int i=3; i<=n; i++) {
//            dp[i][1] = Math.max(dp[i-2][1], dp[i-2][2]) + s[i];
//            dp[i][2] = dp[i-1][1] + s[i];
//        }
//        System.out.println(Math.max(dp[n][1], dp[n][2]));
//    }
}