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

문제

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

2579번: 계단 오르기

 

 

풀이

1로 만들기 같은 유형의 DP 문제이다.

https://seokmimmmmmmmm.tistory.com/82

[백준]1463번 1로 만들기 - Java

 

1로 만들기 문제의 경우, 처음부터 생각하는게 아니라 목적인 1에서부터 거꾸로 생각하는 느낌?? 이였는데 이번 문제도 마찬가지이다.

세개의 계단을 연속으로 밟지 못하므로 마지막 계단(n번째 계단)에 도착하는 방법은 [n-3번째 계단과 n-1번째 계단을 밟고 마지막을 밟는 방법]과 [n-2번째 계단을 밟고 마지막을 밟는 방법] 이렇게 두 가지로 나눌 수 있다. 

1로 만들기 문제에서는 1로 만드는 방법이 2로 나누는 방법, 3으로 나누는 방법이 있던거랑 비슷한 맥락이라고 생각하면 된다.

 

초기값은 계단이 3개일 때까지니까 dp[3]까진 초기값으로 채워주고 시작한다.

주의할 점은 [n-3번째 계단과 n-1번째 계단을 밟고 마지막을 밟는 방법]에서 n-3번째 계단은 dp배열에서, n-1번째 계단은 그냥 arr배열에서 가져와야한다는 점이다!

 

 

코드

// 2579번 계단 오르기
// https://www.acmicpc.net/problem/2579

package BAEKJOON;

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

public class Num2579_계단오르기 {
    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[N + 1];
        int[] dp = new int[N + 1];

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

        dp[1] = arr[1];
        dp[2] = arr[2] + arr[1];
        dp[3] = arr[3] + Math.max(arr[1], arr[2]);

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

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