[JAVA] 백준 2579번- 계단 오르기

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

2579번: 계단 오르기

 

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[301];
        int[] dp = new int[301];

        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];

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

 

 

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

 

계단의 수가 n개라고 할 때, 이 규칙을 성립시키려면

 

n번째 계단을 밟는 경우의 수는

n-3번째 계단 -> n-1번째 계단 -> n번째 계단

n-2번째 계단 -> n번째 계단

 

이렇게 두가지이다. 

그러므로 n번째 계단을 밟을 때 점수의 최댓값은

 

((n-3)번째 계단까지의 점수 최댓값 + (n-1)번째 계단의 점수) 와 (n-2)번째 계단까지의 최댓값

이 두가지 경우 중 더 큰 값에 n번째 계단의 점수를 더한 값이다. 

 

이를 점화식으로 나타내면 이렇게 표현할 수 있다.

 

 

dp[n] = n번째 계단을 밟을 때 점수의 최댓값
dp[n] = Math.max(dp[n-3]+arr[i-1], dp[n-2]) + arr[i]