문제
길이 L인 롤 케이크를 N명의 방청객에게 나눠준다. 각 방청객이 원하는 구간이 주어지고, 먼저 선택한 사람이 우선권을 갖는다. 가장 많은 조각을 받을 것으로 기대한 사람과, 실제로 가장 많이 받은 사람의 번호를 구하라.
입력
첫째 줄에 롤 케이크 길이 L, 둘째 줄에 방청객 수 N이 주어진다. 이후 N줄에 각 방청객이 원하는 범위 P, K가 주어진다.
출력
첫째 줄에 기대한 조각 수가 가장 많은 사람 번호, 둘째 줄에 실제로 받은 조각 수가 가장 많은 사람 번호를 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 3 2 4 7 8 1 6 | 3 1 |
풀이
배열로 롤 케이크를 표현하여, 선착순으로 배분하며 기대/실제 최다 수령자를 추적한다.
- 각 방청객의 기대 조각 수(K-P)를 계산하여 최대값을 가진 사람을 기록한다
- 길이 L 배열에서, 각 방청객의 구간 P~K 중 아직 0인 칸만 배분하고 실제 받은 수를 센다
- 실제 받은 수의 최대값을 가진 사람을 기록한다
핵심 아이디어: 기대값은 단순히 구간 길이(K-P)로 결정되고, 실제 배분은 먼저 선택한 사람이 우선이므로 배열에 이미 배정된 칸(!=0)은 건너뛴다.
코드
package com.ssafy.an.day049;
import java.util.Scanner;
public class Day09BOJ3985롤케이크 { // 3985
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int max = 0; // 희망 최고
int maxSum = 0; // 실제 최고
int p1 = 0; // 사람 번호 계산시 + 1
int p2 = 0;
int L = sc.nextInt();
int N = sc.nextInt();
int arr[] = new int[L];
for (int i = 0; i < N; i++) {
int P = sc.nextInt();
int K = sc.nextInt();
int sum = 0;
if ((K - P) > max) {
max = (K - P);
p1 = i + 1;
}
for (int j = P - 1; j < K; j++) {
if (arr[j] == 0) { // 0이 아닐때만 숫자 부여
arr[j] = (i + 1);
sum++; // 결국 자기 숫자가 배열에 많이 들어가야 함
}
}
if (sum > maxSum) {
p2 = (i + 1);
maxSum = sum;
} // 같으면 먼저 반영된 사람이기때문에 = 미포함
}
System.out.println(p1);
System.out.println(p2);
sc.close();
}
}복잡도
- 시간: O(N * L) — N명의 방청객이 각각 최대 L칸을 확인
- 공간: O(L) — 롤 케이크 배열