본문 바로가기

알고리즘 Algorithm/BOJ 백준 (초급~중급)

[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

링크 : https://www.acmicpc.net/problem/11062 문제 설명 : 더보기 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈

subbak2.tistory.com

 

카드게임을 먼저 풀어봤다면, 환형 데이터 구조를 어떻게 처리할지와, 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;
	}
}
반응형