[Algo] 백준 23029 시식 코너는 나의 것 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/23029

메모리 : 27184KB

시간 : 252ms

언어 : Java 11

---

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[100001];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        long[][] dp = new long[100001][3]; // 1턴 2턴 3턴
        dp[1][0] = 0;
        dp[1][1] = dp[1][2] = arr[1];
        dp[2][0] = arr[2];
        dp[2][1] = arr[1] + arr[2] / 2;
        dp[2][2] = arr[1];
        long ans = Math.max(dp[2][0], dp[2][1]);
        for (int i = 3; i <= N; i++) {
            dp[i][0] = dp[i - 1][2] + arr[i]; // 첫번째 다먹기
            dp[i][1] = dp[i - 1][0] + arr[i] / 2; // 두번째 절반먹기
            dp[i][2] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][0]); // 세번째 쉬어가기
        }
        ans = Math.max(Math.max(dp[N][0], dp[N][1]), dp[N][2]);
        System.out.println(ans);
    }
}

풀이

1번째, 2번째, 3번째 시식에서의 행동이 다르니 2차원 DP에 저장해주며 그 중 가장 큰 수만을 저장한다.

세 칸이 한 풀이에 사용되므로 1차원 dp로도 해결 가능한 문제였다.

0	1	2	3
O	X	O	O
X	O	X	O
X	X	O	O

다음과 같이 먹을 수 있기 떄문에 이를 점화식을 써서 풀면 1차원 배열로도 풀 수 있다.