[백준] 3985번: 롤 케이크(구현, 시뮬레이션)

https://www.acmicpc.net/problem/3985

3985번: 롤 케이크

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int L = scan.nextInt();	// 롤케이크 길이
		int N = scan.nextInt();	// 방청객의 수
		boolean[] cake = new boolean[L+1];	// 롤케이크 길이+1 배열 선언
		int[] getCake = new int[N+1];
		int[][] arr = new int[N][2];
		int maxIndex = 0;	// 가장 많은 조각 기대한 방청객 
		int maxCake = 0;	// 실제 가장 많은 조각 받은 방청객
		for(int i=0; i<N; i++) {
			arr[i][0] = scan.nextInt();
			arr[i][1] = scan.nextInt();
		}
		
		// 가장 많은 조각을 받을 것으로 기대한 케이크의 조각 수 찾기
		for(int i=0; i<N; i++) {
			if(arr[i][1] - arr[i][0] > maxIndex)
				maxIndex = arr[i][1] - arr[i][0];
		}
		
		// 실제 가장 많은 조각 받은 방청객 찾기
		for(int i=1; i<=N; i++) {
			for(int j=arr[i-1][0]; j<=arr[i-1][1]; j++) {
				if(!cake[j]) {	// 방청객이 기대한 번호가 체크가 안되어 있는경우
					getCake[i] ++;	// i번째 방청객 케이크 +1
					cake[j] = true;	// 케이크를 받았으므로 체크표시
				}
			}
		}
		
		// 방청객 중 가장 많은 조각을 받은 케이크 수 찾기
		for(int i=1; i<getCake.length; i++) {
			if(getCake[i] > maxCake)
				maxCake = getCake[i];
		}
		
		// 가장 많은 조각을 받을 것으로 기대하고 있던 방청객이 여러명인 경우 => 번호가 작은 사람 출력
		for(int i=1; i<=N; i++) {
			if(maxIndex == arr[i-1][1] - arr[i-1][0]) {
				System.out.println(i);
				break;
			}
		}
		// 실제 가장 많은 조각을 받은 방청객이 여러명인 경우 => 번호가 작은 사람 출력
		for(int i=1; i<getCake.length; i++)
			if(getCake[i] == maxCake) {
				System.out.println(i);
				break;
			}
				
		scan.close();
	}

}

풀이

 

문제의 조건대로 그대로 구현하려다 보니 좀 복잡해진 것 같다.

문제에서 가장 많은 조각을 받을 것으로 기대하는 방청객이나 실제 가장 많은 조각을 받은 방청객이 여러명일 수 있는데, 이때 번호가 작은 사람을 출력해야 한다.

그래서 접근방법은,

 

1) 가장 많은 조각을 받을 것으로 기대한 케이크의 조각 수를 찾는다.

		for(int i=0; i<N; i++) 
			if(arr[i][1] - arr[i][0] > maxIndex)
				maxIndex = arr[i][1] - arr[i][0];

 

 

2) 실제 가장 많은 조각 받은 방청객을 찾는다.

		for(int i=1; i<=N; i++) {
			for(int j=arr[i-1][0]; j<=arr[i-1][1]; j++) {
				if(!cake[j]) {	// 방청객이 기대한 번호가 체크가 안되어 있는경우
					getCake[i] ++;	// i번째 방청객 케이크 +1
					cake[j] = true;	// 케이크를 받았으므로 체크표시
				}
			}
		}

방청객 순으로 해서 P번 ~ K번 조각 까지 만약 체크가 되어있지 않으면 

그 방청객은 그 케이크조각을 얻을 수 있으므로 +1 하고, 체크 표시를 한다.

 

 

3) 위에서 계산한 가장 많은 방청객을 통해 가장 많은 조각을 받은 케이크는 몇조각인지 찾는다.

		for(int i=1; i<getCake.length; i++) 
			if(getCake[i] > maxCake)
				maxCake = getCake[i];

 

 

4) 위 작업이 끝난 후 방청객이 여러명일 경우 가장 작은 번호를 출력하고 종료한다.

		for(int i=1; i<=N; i++) {
			if(maxIndex == arr[i-1][1] - arr[i-1][0]) {
				System.out.println(i);
				break;
			}
		}
        
        
       	 	for(int i=1; i<getCake.length; i++) {
			if(getCake[i] == maxCake) {
				System.out.println(i);
				break;
			}
		}