백준(BOJ) 2579 : 계단 오르기 (JAVA)

문제링크 : https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

필자는 이 문제의 출처가 정보올림피아드 '초등부'라는 걸 알았는데 꽤나 충격을 받았다... 난 초등학교 때 뭐했지...ㅠㅠ 각설하고, 설명을 해보도록 하겠다.

 

이 문제는 메모이제이션을 통한 다이나믹 프로그래밍 문제이다. 그렇다면 대체 무엇을 메모리에 남겨야할까?! 바로 각 계단까지 올라왔을 때의 점수의 최댓값이다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] scores = new int[300];
        int[] max = new int[300];
        
        for(int i = 0; i < n; i++) {
            scores[i] = Integer.parseInt(br.readLine());
        }
        
        max[0] = scores[0];
        max[1] = scores[0] + scores[1];
        max[2] = Math.max(scores[0], scores[1]) + scores[2];
        
        for(int i = 3; i < n; i++) {
            max[i] = Math.max(max[i - 2], max[i - 3] + scores[i - 1]) + scores[i];
        }
        
        System.out.println(max[n - 1]);
    }
}