백준 2579 계단 오르기 - JAVA

2579 문제 링크

---

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

 

문제 설명

---

 

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] arr;
    static Integer[] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        dp = new Integer[n + 1];
        
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        dp[0] = arr[0];
        dp[1] = arr[1];
        if(n >= 2) {
            dp[2] = arr[1] + arr[2];    
        }
        bw.write(String.valueOf(findMax(n)));
        bw.flush();
    }
    
    private static int findMax(int n) {
        if(dp[n] == null) {
            dp[n] = Math.max(findMax(n-2), findMax(n-3) + arr[n-1]) + arr[n];
        }
        
        return dp[n];
    }
}

 

알고리즘 설명

---

해당 문제는 저도 오래 고민하다가, 초등부 올림피아드 출제 문제라는 것을 보고 바로, 연습장을 꺼내 경우의 수를 적기 시작했습니다.
어떤걸 기준으로 경우의 수를 적을까 하다가, 마지막 계단을 밟아야 한다는 문제의 말을 보고, dp배열을 생성해 1부터 N까지 dp[N]에 올 수 있는 경우를 적었습니다. 예를 들어 N = 5의 경우, 최댓값을 가지기 위해 밟을 수 있는 계단은 3번째 계단과 4번째 계단뿐입니다. 그렇다면 dp[5] 즉, 5번째 계단까지의 최댓값은 dp[3]까지의 값과 dp[2] + arr[4] 중에서 더 큰 값을 고르면 되는 간단한 문제였습니다. dp[4]가 아니고 dp[2] + arr[4]인 이유는 간단합니다. 연속으로 3개의 계단을 밟을 수 없기때문에, 4를 통해 5번째 계단으로 가는 방법은 2 → 4 → 5 밖에 없기 때문에, dp[3]의 값이 들어가버리는 경우 3개의 계단을 연속으로 밟아버리는 경우의 수를 포함하기 때문에, dp[2]까지의 값과 3을 건너뛴 arr[4]의 값을 더하는 것입니다. top-down방식과 bottom-up방식 모두 가능하지만, 코드의 큰 차이는 없기 때문에 top-down방식으로 진행했습니다.

 

코드 해석

---

배열 원소를 지칭하는 번호와 계단의 번호를 맞추기 위해 1-base-position으로 arr 배열과 누적값을 넣을 dp 배열 을 생성합니다. arr 배열에 n번째 계단까지의 값을 넣어주고, dp[0] = 0 (자료형이 Integer이므로 기본값은 null), dp[1] = arr[1], dp[2] = arr[2]를 설정해주고, findMax함수를 생성해, n이 3이상인 경우, 알고리즘 설명의 점화식을 대입해서 dp[n]의 값을 구합니다.