21.09.20 기록

백준 알고리즘 2579 풀이

🎆나의 오답

-DP 풀이를 도전해봤으나 오늘도 조건에서 막혀서 풀지 못했다🙄

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B2579 {
    public static int N;
    public static int[] score;
    public static Integer[] dp;
    public static int stepCnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 Integer[N+1];
        System.out.println(Math.max(getMax(1, 1), getMax(2, 2)));
    }

    public static int getMax(int idx, int step) {
        if(step == 1) {
            stepCnt += step;
        }
        if((stepCnt == 3 && idx != 3) || idx > N) {
            return 0;
        }

        if(idx == N) {
            return dp[idx] = score[idx];
        }

        if(dp[idx] == null) {
            dp[idx] = Math.max(getMax(idx+1, 1), getMax(idx+2, 2)) + score[idx];
        }

        return dp[idx];
    }
}

🎆해설(메모리 14.2MB, 시간 124ms로 통과)

-과정을 손으로 직접 그려봤지만 getMax(N-3) + score[N-1] 부분은 여전히 모르겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B2579 {
    public static Integer dp[];
    public static int score[];

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

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

        for (int i = 1; i <= N; i++) {
            score[i] = Integer.parseInt(br.readLine());
        }

        dp[0] = score[0];
        dp[1] = score[1];

        if (N >= 2) {
            dp[2] = score[1] + score[2];
        }

        System.out.println(getMax(N));
    }

    public static int getMax(int N) {
        if(dp[N] == null) {
            //연속된 블럭의 경우의 수를 위해 이미 입력받은 배열의 값을 더해준다.
            dp[N] = Math.max(getMax(N-2), getMax(N-3) + score[N-1]) + score[N];
        }
        return dp[N];
    }
}