[백준] 계단 오르기 : 2579 : Java - DP (S3)

1.  💎 문제

2579번: 계단 오르기

 

• 한 계단, 두 계단 씩만 이동 가능
• 연속한 3개의 계단 불가
• 마지막 계단 반드시 밟음
• 얻을 수 있는 총 점수의 최댓값 구하기

 

 

2.  🤔 풀이 생각 

이 문제의 핵심은 2계단을 가면 무조건 이동해야 한다는 것이다. 3 계단을 가지 전에 끊어줘야 하므로, 현재 계단에서 선택할 수 있는 경우의 수는 2가지뿐이다.

 

    1. 직전의 계단(n-1)을 밟고 현재 계단을(n)을 밟는다.

    2.두 번째 전 계단(n-2)을 밟고 현재 계단(n)을 밟는다.

 

여기서 1번은 세 계단을 이어서 밟을 수 없다는 조건을 고려해야 한다. 그러므로 n-3 계단을 밟고 n-1 계단을 밟는경우로 계산해줘야 한다.

두 가지 경우의 수중 더 높은 포인트를 얻는 계단을 선택한다. 2번에서는 이미 간격차이가 일어나므로 이어서 밟을 수 없다는 조건을 확인할 필요 없다. 두 경우 중 더 높은 것을 택한다.

 for(int i=3; i<= N; i++){
            dp[i] = Math.max(dp[i-3] + nums[i-1],dp[i-2]) + nums[i];
        }

 

 

3.  📄 전체 코드

import java.io.*;

public class Main {

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

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

        int N = Integer.parseInt(br.readLine());
        int nums [] = new int[301];
        int [] dp = new int[301];
        for(int i =1; i<=N; i++){
            nums[i] = Integer.parseInt(br.readLine());
        }
        dp[1] = nums[1];
        dp[2] = nums[1] + nums[2];

        for(int i=3; i<= N; i++){
            dp[i] = Math.max(dp[i-3] + nums[i-1],dp[i-2]) + nums[i];
        }
        bw.write(dp[N]+"\n");

        bw.flush();

        bw.close();
        br.close();
    }


}