DP :: 백준 :: 계단 오르기 :: 2579

계단오르기 2579

https://www.acmicpc.net/problem/2579

[문제 풀이]

i번째 계단을 밟았을 때 최댓값은 두 경우

  - i-2번째 계단 밟고 i번째 밟을 경우

  - i-1번째 계단 밟고 i번째 밟을 경우

중 최댓값을 고르면 답!!??

이 아니라 틀린다!!

2번조건 "연속된 세 개의 계단을 밟으면 안된다"는 조건이 있기 때문이다!

자, 그러면 어떻게 풀어야 할까?

일단 2차원 배열을 생성한다.

i번째 계단을 밟았을 때 

  1) 1번 연속으로 밟은 경우 : dp[1][i]

  2) 2번 연속으로 밟은 경우 : dp[2][i]

두 경우로 나눌 수 있다!

이때, 

1) i번째 계단을 1번 연속으로 밟기 위해서는 i-2번째 계단에서 2칸 이동하는 방법밖에 없으므로

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

   이렇게 계산할 수 있고

2) i번째 계단을 2번 연속으로 밟기 위해서는 i-1번째 계단에서 1칸 이동하는 방법밖에 없으므로

        dp[2][i] = dp[1][i-1]+score[i]

   이렇게 계산할 수 있다.

i번까지 모두 계산한 후

max(dp[1][i], dp[2][i]) 출력하면 끝!!

import java.io.BufferedReader;
import java.io.InputStreamReader;
  
public class Main {
    static int[] stair = new int[301];
    static int[][] dp = new int[3][301];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        for(int i=1;i<=num;i++){
            stair[i] = Integer.parseInt(br.readLine());;
        }
        upstair(num);
        System.out.println(Math.max(dp[1][num], dp[2][num]));
    }
     
    public static void upstair(int num){
        dp[1][1] = stair[1];
        for(int i=2;i<=num;i++){
            dp[1][i] = Math.max(dp[2][i-2], dp[1][i-2])+stair[i];
            dp[2][i] = dp[1][i-1]+stair[i];
        }
    }
}