[백준] No2579-계단오르기 (JAVA)

일반적인 dp문제 + 연속해서 3개의 계단을 밟을 수 없다는 조건이 더해진 문제이다.

max[i]를 i번째 계단을 밟았을때까지 얻을 수 있는 점수의 최댓값이라고 하면,

max[i]= stairs[i]+ Math.max(max[i-2],stairs[i-1]+max[i-3])

이라는 점화식이 나온다.

풀어서 보자면, i번째 계단을 밟는 경우의수는 총 2가지이다.

• 2칸 아래의 계단을 밟은 후에 i번째 계단을 밟기
• 1칸 아래의 계단을 밟은 후에 i번째 계단을 밟기

💯 문제에서 연속된 3개의 계단을 모두 밟을 수는 없다고 했으므로 1칸 아래의 계단을 밟은 경우에는 무조건 그전에 2칸아래의 계단을 밟은 경우여야만 한다.

import java.io.*;

public class No2579_계단오르기 {
    static int max[];
    static int stairs[];
        public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            stairs = new int[310];
            max= new int[310];
            for (int i=1;i<=n;i++) {
                stairs[i]=Integer.parseInt(br.readLine());
            }

            max[1] = stairs[1];
            max[2] = stairs[1]+stairs[2];
            max[3] = stairs[3]+ Math.max(stairs[1],stairs[2]);

           for (int i=4;i<=n;i++) {
               max[i]= Math.max(max[i-2],stairs[i-1]+max[i-3])+stairs[i];
           }
            System.out.println(max[n]);
        }

    }