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

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

2579번: 계단 오르기

풀이

최근에 풀어본 포도주 시식 문제(2156번)와 거의 똑같아서 점화식을 바로 찾을 수 있었다.

이 문제에서 제공하는 조건은 총 3가지이다.

 

1. 한 계단 혹은 두 계단을 오를 수 있다.

2. 연속된 3개의 계단은 밟을 수 없다.

3. 마지막 계단은 반드시 밟아야한다.

 

쉽게 생각해서 i번째 칸에 대해서 두 칸 전(i-2) + 현재 칸(i) 와 세 칸 전(i-3) + 한 칸 전(i-1) + 현재 칸(i)를 비교하면 된다.

 

동적 계획법에는 Bottom-up 방식과 Top-Down 방식이 있다. 필자는 Bottom-up 방식으로 문제를 해결했다.

즉, 반복문을 사용해서 풀었는데 주의할 점은 한 가지다.

 

점화식을 보면 알 수 있듯이 dp[i-3], dp[i-2]가 존재한다. 그렇기 때문에 세 번째의 경우부터 점화식을 적용시킬 수 있다. 이를 생각하지 않고 0부터 돌리게 된다면 ArrayIndexOutOfBoundException이 발생할 것이다.

 

자세한 내용은 포도주 시식 문제를 보면 쉽게 이해할 수 있다.

[백준]JAVA - 2156번: 포도주 시식

import java.io.*;

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[N+1];
        int[] dp = new int[N+1];
        for (int i=1; i<N+1; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
		
        dp[0] = 0;
        dp[1] = arr[1];
		
        if (N > 1) dp[2] = arr[1] + arr[2];
		
        for (int i=3; i<N+1; i++) {
            dp[i] = Math.max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]);
        }
		
        System.out.println(dp[N]);
    }
}