[ BOJ ][JAVA][10714] 케이크 자르기 2

www.acmicpc.net/problem/10714

10714번: 케이크 자르기 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	552	272	210	54.974%

문제

JOI 군과 IOI 양은 쌍둥이 남매이다. JOI 군은 최근 과자 만들기에 푹 빠졌기 때문에, JOI 군은 오늘도 케이크를 만들어서 먹으려고 했지만, 막 구워진 참에 냄새를 맡고 온 IOI 양이 왔기 때문에 두 명이 케이크를 나누어 먹기로 했다.

케이크는 둥그런 모양을 하고 있다. 어느 점에서부터 직선으로 칼집을 넣어 케이크를 N 개의 조각으로 나눈 뒤, 각 조각마다 1부터 N 까지 반시계방향으로 번호를 매긴다. 즉, 1 ≦ i ≦ N에 대해, i 번째 조각은 i - 1 번째와 i + 1 번째 조각과 인접해있다. (단, 0번째는 N 번째, N + 1 번째는 1번째로 간주한다). i 번째 조각의 크기는 Ai 이지만, 칼질이 서툴러 Ai가 모두 다른 값을 가지게 되었다.

그림 1 : 케이크의 예 (N = 5, A1 = 2, A2 = 8, A3 = 1, A4 = 10, A5 = 9)

이 N개를 JOI 군과 IOI 양이 나누기로 하였다. 나누는 방법은 다음과 같다.

1. 먼저, JOI 군이 N 개의 조각 중 원하는 것 하나를 가져간다.
2. 그 뒤, IOI 양으로부터 시작해 IOI 양과 JOI 군은 번갈아가며 남은 조각을 하나씩 가져간다. 단, 인접한 조각 중 하나 이상의 조각이 이미 선택된 경우에만 가져갈 수 있다. 가져갈 수 있는 조각이 여러 개 있을 때엔, IOI 양은 그 중 가장 큰 조각을 가져가고, JOI 군은 원하는 조각을 가져갈 수 있다.

JOI 군은 자신이 가져온 조각들 크기의 합을 최대화하고 싶다.

케이크의 조각 수 N 과, N 개의 조각의 크기에 대한 정보가 주어질 때, JOI 군이 가져올 수 있는 조각들의 합계의 최대치를 구하는 프로그램을 작성하시오.

입력

표준입력으로부터 이하의 입력이 주어진다.

• 첫 번째 줄에는 케이크가 N 개의 조각으로 나뉘어 있음을 나타내는 정수 N이 주어진다.
• 이어지는 N 열 중 i 열 (1 ≦ i ≦ N) 에는 i 번째 조각의 크기를 나타내는 정수 Ai가 적혀있다.

모든 입력 데이터는 아래의 조건을 만족한다.

• 1 ≦ N ≦ 2 000．
• 1 ≦ Ai ≦ 1 000 000 000．
• Ai 모두 다른 값을 갖는다.

출력

JOI 군이 가져올 수 있는 조각들의 합계의 최대치를 한 줄로 출력하시오.

예제 입력 1

5
2
8
1
10
9

예제 출력 1

18

예제 입력 2

8
1
10
4
5
6
2
9
3

예제 출력 2

26

예제 입력 3

15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789

예제 출력 3

3600242976

코드

/*
    케이크 자르기2
    DP + DFS
    카드게임과 유사하다.

    dp[l][r] : 현재까지 가져간 가장 왼쪽 위치 l, 가장 오른쪽 위치 r에서의 최대값

    i양이 먹을 차례에서는 (l-1)번쨰와 (r+1)번째 중 더 큰 값을 가져가면된다.
    j군이 먹을 차례에서는 (l-1)번째와 (r+1)번째를 가져갔을때 최종적으로 더 큰 결과를 갖게 되는 쪽을 가지면 된다.
*/
import java.io.*;
import java.util.*;
public class p10714 {
    static int n;
    static long[] arr;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        dp = new long[2020][2020];
        for (int i = 0; i < 2020; i++) {
            Arrays.fill(dp[i], -1);
        }
        long answer = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            answer = Math.max(answer, arr[i] + go(0, Minus(i), Plus(i)));
        }
        sb.append(answer);
        System.out.println(sb.toString());
    }
    static long go(int turn, int l, int r) {
        if (l == r) {
            if (turn == 1) return arr[l];
            else return 0;
        }

        long ret = dp[l][r];
        if (ret != -1) return ret;
        else { ret = 0; }

        if  (turn == 1) {
            ret += Math.max(arr[l] + go(0, Minus(l), r), arr[r] + go(0, l, Plus(r)));
        } else {
            if (arr[l] > arr[r]) {
                ret += go(1, Minus(l), r);
            } else {
                ret += go(1, l, Plus(r));
            }
        }
        dp[l][r] = ret;
        return ret;
    }

    static int Plus(int x) {
        return (x + 1) % n;
    }

    static int Minus(int x) {
        return (x + n - 1) % n;
    }

}

다른 풀이

import java.io.*;
import java.util.*;
public class Main {
    static int n;
    static long[] arr;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        dp = new long[2020][2020];
        for (int i = 0; i < 2020; i++) {
            Arrays.fill(dp[i], -1);
        }
        long answer = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            answer = Math.max(answer, arr[i] + ioi(i, i));
        }
        sb.append(answer);
        System.out.println(sb.toString());
    }

    // I양이 먹을 차례인데 I양이 먹을 수 있는값
    // => I양이 먹을 차례일 때 J군이 많이 먹을 수 있는 값
    static long ioi(int l, int r) {
        // I양이 먹으면 J군이 먹을 수 있는건 0이므로
        if (Plus(r) == l) return 0;
        if (arr[Minus(l)] > arr[Plus(r)]) return joi(Minus(l), r);
        return joi(l, Plus(r));
    }

    // J군이 먹을 차례인데 왼쪽은 l번 조각과 오른쪽 r번조각이 있을 때 J군이 가장 많이 먹는 경우
    static long joi(int l, int r) {
        if (dp[l][r] != -1) return dp[l][r];
        if (Plus(r) == l) return dp[l][r] = 0;
        long t1 = arr[Minus(l)] + ioi(Minus(l), r);
        long t2 = arr[Plus(r)] + ioi(l, Plus(r));
        if (t1 > t2) return dp[l][r] = t1;
        return dp[l][r] = t2;
    }

    static int Plus(int x) {
        return (x + 1) % n;
    }

    static int Minus(int x) {
        return (x + n - 1) % n;
    }

}