백준 - 2579

import java.io.*;

public class Main {
    static int[] score;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        score = new int[N+1];
        for(int i = 1; i <= N; i++){
            score[i] = Integer.parseInt(br.readLine());
        }
        dp = new int[N+1];
        System.out.println(floor(N));
    }
    static int floor(int stair){
        if(stair == 0) return 0;
        if(stair == 1) return score[1];
        if(stair == 2) return score[1] + score[2];
        if(dp[stair] != 0) return dp[stair];
        dp[stair] = Math.max(
                floor(stair-2) + score[stair],
                floor(stair-3) + score[stair-1] + score[stair]
        );
        return dp[stair];
    }
}

풀이과정 및 리뷰

조건

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. → fx(n-2) + n

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

   → fx(n-3) + n-1 + n

해당 두개 식 중 max값을 구해 리턴하도록 점화식 설계

초기값

0일 때 → return 0

1일 때 → return score[1]

2일 때 → return score[1] + score[2]

3번째부터는 점화식 사용해 재귀호출 시작

처음 시도 : if(dp[stair] != 0) return dp[stair]; 코드가 없었음
→ 이미 최대값을 구해 저장하려는 배열을 선언했음에도 불구하고 사용하지 않음. 따라서 매번 재귀호출을 통해 제일 하위값들을 매 호출마다 계산했음 .

→ 메모이제이션 없이 재귀로 풀면 약 O(2ⁿ)에 가까운 호출이 생겨서, N = 300이면 재귀 호출이 지수적으로 폭발하고 스택오버플로우 발생

n (계단 수)	호출 횟수 (최악)
10	약 100번 미만
20	약 7,000번 이상
30	약 100,000번 이상
40	약 1,000,000번 이상
300	💥 완전히 터짐 (2ⁿ 수준)

두번째 시도 : 해당 코드 추가로, 연산한 값들을 저장해 그 값을 불러옴

보완점

Arrays.fill(dp, -1); if (dp[stair] != -1) return dp[stair]; 사용시, 확실하게 사용하지 않는 값을 넣어두고 조건 체크 가능