[Java] 백준 2579 계단 오르기

 

문제

계단을 밟으면 해당 계단에 쓰인 점수를 얻을 수 있다고 할 때,

얻을 수 있는 점수의 최댓값을 구하는 문제이다.

 

규칙

- 한 번에 1계단 or 2계단
- 연속 3계단 불가능
- 시작점은 계단 아님
- 도착점은 반드시 밟기

 

 

풀이

현재 위치가 n번째 계단이라고 할 때, n번째 계단에서 얻을 수 있는 점수의 최댓값을 생각해보자.

연속 3칸을 밟은 것은 불가능하기 때문에 고려해야할 경우는 2가지이다.

1) n-2번째 계단을 밟은 뒤 n번째 계단을 밟은 경우 

- dp[n-2] + scores[n]

2) n-3번째 계단을 밟은 뒤 n-1번째 계단을 밟고 n번째 계단을 밟은 경우

- dp[n-3] + scores[n-1] + scores[n]

즉, 다음의 두 가지 경우 중 큰 값으로 dp[n]을 초기화 시키면 된다.

 

 

 

코드

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[] scores = new int[301];
        int[] dp = new int[301];
        for (int i = 1; i <= N; i++) {
            dp[i] = scores[i] = Integer.parseInt(br.readLine());
        }
        dp[2] += scores[1];

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

        System.out.println(dp[N]);
    }
}