[BOJ 백준] 케이크 자르기2 (10714) Java

링크 : https://www.acmicpc.net/problem/10714

 

문제 설명 : 

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 군이 가져올 수 있는 조각들의 합계의 최대치를 한 줄로 출력하시오.

 

 

예제 입력 : 

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

 

예제 출력 : 

3600242976

 

 

접근법 : 

1) 어떻게 풀 것인가?

백준 11062 카드게임과 거의 유사한 문제이다.

 

https://subbak2.tistory.com/78

[BOJ 백준] 카드 게임 (11062) Java

 

카드게임을 먼저 풀어봤다면, 환형 데이터 구조를 어떻게 처리할지와, joi, ioi의 다른 점을 어떻게 구현할지 생각하면 되는 문제이다.

 

케이크 환형 구조는 아래와 같이 구현했다.

static int goRight(int id) {
		return (id + 1) % N;
	}

static int goLeft(int id) {
	return (id + N - 1) % N;
}

전체 코드는 아래 참고.

 

2) 시간복잡도

O(N^2)으로 무리 없음

(Java 기준 - 460ms)

 

3) 공간복잡도

N이 2,000으로 크지 않아 고려하지 않음

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

분할정복 코드 작성법. 환형 데이터 구조.

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 10714 케이크 자르기2
public class Main {

	static int N;
	static int[] input;
	static long[][] dp; // dp[l][r] 가져간 가장 왼쪽 위치 l, 가장 오른쪽 위치 r

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		input = new int[N];
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(br.readLine());
		}
		dp = new long[N+1][N+1];
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				dp[i][j] = -1;
			}
		}

		long ans = 0;
		for (int i = 0; i < N; i++) {
			ans = Math.max(ans, input[i] + ioi(i, i));
		}
		bw.write(String.valueOf(ans));

		bw.flush();
		bw.close();
		br.close();
	}

	static long ioi(int left, int right) {
		// 1. 가장 끝까지 왔으면
		if (goRight(right) == left) {
			return 0;
		}
		// 2. 왼쪽이 더 크면 왼쪽으로
		if (input[goLeft(left)] > input[goRight(right)]) {
			return joi(goLeft(left), right);
		}
		// 3. 아니면 오른쪽으로
		return joi(left, goRight(right));
	}

	static long joi(int left, int right) {
		// 1. 가장 끝까지 왔으면
		if (goRight(right) == left) {
			return dp[left][right] = 0;
		}
		// 2. 갱신이 됐으면
		if (dp[left][right] != -1) {
			return dp[left][right];
		}
		// 3. left / right 뿌린 것 합침
		long leftV = input[goLeft(left)] + ioi(goLeft(left), right);
		long rightV = input[goRight(right)] + ioi(left, goRight(right));

		return dp[left][right] = Math.max(leftV, rightV);
	}

	static int goRight(int id) {
		return (id + 1) % N;
	}

	static int goLeft(int id) {
		return (id + N - 1) % N;
	}
}