인기 티비 프로그램 "나는 요리사 인가?"의 새 시즌이 시작한다. 이번 시즌은 기네스북에 등재될 만한 음식을 만드는 것을 목표로 진행한다. 첫 번째 에피소드에 출연하는 요리사는 전설의 요리사 김상근이고, 길이 L미터의 롤 케이크를 만들 것이다. 상근은 몇 시간동안 집중해서 케이크를 만들었고, 이제 스튜디오의 방청객 N명에게 케이크를 나누어 주려고 한다. 상근이는 롤 케이크를 펼쳐서 1미터 단위로 잘라 놓았다. 가장 왼쪽 조각이 1번, 오른쪽 조각이 L번 조각이다. 방청객은 1번부터 N번까지 번호가 매겨져 있다. 각 방청객은 종이에 자신이 원하는 조각을 적어서 낸다.이때, 두 수 P와 K를 적어서 내며, P번 조각부터 K번 조각을 원한다는 뜻이다. 프로그램의 진행자 고창영은 1번 방청객의 종이부터 순서대로 펼쳐서 해당하는 조각에 그 사람의 번호를 적을 것이다. 이때, 이미 번호가 적혀있는 조각은 번호를 적지 못하고 넘어간다.이런 방식을 이용해서 방청객에게 조각을 주다보니, 자신이 원래 원했던 조각을 받지 못하는 경우가 생길 수 있다. 아래 그림은 이 문제의 예제를 나타낸 것이다. 가장 많은 케이크 조각을 받을 것으로 기대한 방청객의 번호와 실제로 가장 많은 케이크 조각을 받는 방청객의 번호를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 롤 케이크의 길이 L (1 ≤ L ≤ 1000)이 주어진다. 둘째 줄에는 방청객의 수 N (1 ≤ N ≤ 1000)이 주어진다. 다음 N개 줄에는 각 방청객 i가 종이에 적어낸 수 Pi와 Ki가 주어진다. (1 ≤ Pi ≤ Ki ≤ L, i = 1..N)
출력
첫째 줄에 가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호를 출력한다.
둘째 줄에 실제로 가장 많은 조각을 받은 방청객의 번호를 출력한다.
가장 많은 조각을 받도록 예상되는 방청객이 여러 명인 경우에는 번호가 작은 사람을 출력한다.
예제 입력/출력
예제 입력
예제 출력
10 3 2 4 7 8 6 9
3 1
10 3 1 3 5 7 8 9
1 1
10 5 1 1 1 2 1 3 1 4 7 8
4 5
알고리즘 분류
● 구현
소스코드
package Lv1_Bronze;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* @author HanHoon
* @category 구현
* https://www.acmicpc.net/problem/3985
*/
public class BOJ_B1_3985_롤_케이크 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
// 롤 케이크의 길이
int L = Integer.parseInt(br.readLine());
boolean[] cake = new boolean[L];
// 방청객의 수
int N = Integer.parseInt(br.readLine());
int[] P = new int[N];
int[] K = new int[N];
// 방청객들이 적은 수 P, K (p번~k번 조각을 원함)
int pre_Max_Value = Integer.MIN_VALUE;
int pre_Max_Idx = 0;
int real_Max_Value = Integer.MIN_VALUE;
int real_Max_Idx = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
P[i] = Integer.parseInt(st.nextToken())-1;
K[i] = Integer.parseInt(st.nextToken())-1;
// 가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호
if(pre_Max_Value < (K[i] - P[i] + 1)) {
pre_Max_Value = K[i] - P[i] + 1;
pre_Max_Idx = i;
}
int count = 0;
for (int j = P[i]; j <= K[i]; j++) {
// 케이크가 있는경우에만 나눠준다.
if(cake[j] == false) {
cake[j] = true;
count++;
}
}
// 실제로 가장 많이 받은 방청객의 번호
if(count > real_Max_Value) {
real_Max_Value = count;
real_Max_Idx = i;
}
}
// 배열의 index값으로 넣었으니 실제로는 +1을 해줘야한다.
System.out.println(pre_Max_Idx+1);
System.out.println(real_Max_Idx+1);
br.close();
}
}
댓글