[백준] 2579번: 계단오르기

이 문제는 연속된 세 개의 계산을 모두 밟아서는 안 된다는 조건 때문에 어려웠다🥺 갑쟈기 무서워짐 안녕쟈기

일단 부분 문제는

1. 이전 계단을 밟고 현재 계단을 밟는다
2. 이전 계단을 밟지 않고 현재 계단을 밟는다

중에 더 큰 값을 선택하는 것이다. 나는 2번의 점화식을 세우기가 헷갈렸는데 dp[n-2] 를 이용하면 간단했다. 틀에 박힌 사고 죽어랏

2. 이전 계단을 밟지 않고 현재 계단을 밟는다면~
   👉🏻 dp[n] = dp[n-2] + score[n] 였음.

정답 코드

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

public class Boj2579 {
    public static void main(String[] args) {
        try {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(in.readLine());
            int[] score = new int[300+1];
            int[] dp = new int[300+1];
            for(int i = 1; i <= N; i++) {
                score[i] = Integer.parseInt(in.readLine());
            }
            in.close();
            dp[1] = score[1];
            dp[2] = Math.max(score[1]+score[2], score[2]);
            dp[3] = Math.max(score[1]+score[3], score[2]+score[3]);
            for(int i = 4; i <= N; i++) {
                dp[i] = Math.max(score[i] + score[i-1] + dp[i-3], score[i] + dp[i-2]);
            }
            System.out.println(dp[N]);
        } catch(Exception e) {
            e.printStackTrace();
        }
    }
}