백준 2579 계단오르기 - DP

풀이

기존의 계산식을 재사용하여 더 큰 문제를 풀 수 있으므로 DP로 풀었다.

dp[n] = value 로 n번째칸에서 최대 값 value로 표현할 수 있는데 여기서 조건이 연속으로 3칸 갈 수 없으므로 이차원 배열을 사용해서 풀이했다.

dp[n][cnt] = value , 연속으로 cnt칸 올라갔을때 n번째 칸에서 최대값을 value로 저장하자.

놓친점 1

n==1일때 런타임 에러가 발생했다. DP에서 초깃값이 작을때 정상작동하는지 확인하자.

놓친점 2

글의 조건을 제대로 읽지 않았다.
"연속으로 한칸 또는 두칸 이동한다" 인 조건에 따라 쉬더라도 한번 쉬어야하는데 두번이상 쉴수 있도록 설계했었다. 그래서 3%에서 계속 실패했다.

그에 대한 반례

10
3
5
10
9
2
1
2
5
2
9

코드

import java.io.*;
import java.util.*;



public class Main {


    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());
        if(n==1){
            System.out.println(Integer.parseInt(br.readLine()));
            return ;
        }
        else if (n==2){
            int num1 = Integer.parseInt(br.readLine());
            int num2 = Integer.parseInt(br.readLine());
            System.out.println(num1+num2);
            return ;
        }



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


        int[] scores = new int[n + 1];
        for(int i=0;i<n;i++){
            int score = Integer.parseInt(br.readLine());
            scores[i+1]=score;
        }

        dp[1][1] = scores[1];


        for(int i=2; i<=n;i++){
            int score = scores[i];

            dp[i][1] = Math.max(dp[i-2][1],dp[i-2][2]) + score;
            dp[i][2] = dp[i-1][1] + score;

        }

        System.out.println(Math.max(dp[n][1],dp[n][2]));
    }

    public static int findMax(int[] arr){
        int ret = Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            ret = Math.max(ret, arr[i]);
        }

        return ret;
    }
}