BOJ 2579

import java.util.Scanner;

public class BOJ2579 {
    static int[] score;
    static Integer[] dp; // Integer로 선언하여 null 체크 가능하도록 설정

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        score = new int[n + 1];
        dp = new Integer[n + 1];

        for (int i = 1; i <= n; i++) {
            score[i] = sc.nextInt();
        }

        // 초기값 설정
        dp[0] = 0;
        dp[1] = score[1];
        if (n >= 2) {
            dp[2] = score[1] + score[2];
        }

        System.out.println(MaxScore(n));
    }

    static int MaxScore(int n) {
        // 이미 계산된 값이 있는 경우 반환
        if (dp[n] != null) {
            return dp[n];
        }

        // dp[n]을 계산
        dp[n] = Math.max(MaxScore(n - 2), MaxScore(n - 3) + score[n - 1]) + score[n];
        return dp[n];
    }
}

소감

DP와 관련된 알고리즘 문제 풀이를 진행했는데, 재귀호출을 기반으로 DP 설계하기 위해 많은 시간을 쏟아야 했습니다. 다양한 문제를 접해봐야겠다는 생각이 들었습니다.

처음에 문제를 읽자마자 코드를 작성하기 위해 키보드를 만지기 보다, 생각이 정리될 때까지 펜을 잡고 문제에 접근했다면 조금 더 적은 시간이 걸렸을 것 같다는 생각이 들었습니다.