BOJ 3985 롤케이크

 문제 조건

 

 

문제

 

 

입력

 

 

출력

 

 

문제 분석

- 예상이 되는 사람과 실제 많이 받은 사람을 구분하여 조건에 충족하는 경우 출력하면 간단하다.

 

 

문제 풀이

1) L개의 길이만큼 배열을 생성하고 순차대로 배분(배열의 값을 사람 번호로 저장)한다.

2) 실제 배분된 개수를 계산하여 결과 출력

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static int L, N, expectPiece, expectPerson, ans, temp;
	private static int[][] arr;
	private static int[] res;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		L = Integer.parseInt(br.readLine());
		N = Integer.parseInt(br.readLine());

		arr = new int[N][2];
		res = new int[L];

		expectPiece = Integer.MIN_VALUE;
		temp = Integer.MIN_VALUE;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());

			if (arr[i][1] - arr[i][0] > expectPiece) { // 가장 많은 조각을 받을 수 있는지 비교
				expectPiece = arr[i][1] - arr[i][0]; // 가장 많이 받은 조각 저장
				expectPerson = i + 1; // 해당 방청객 번호 저장
			}
		}

		for (int i = 0; i < N; i++) {
			chk(i, arr[i][0], arr[i][1]);
		}

		System.out.println(expectPerson);
		System.out.println(ans);

	}// main

	private static void chk(int idx, int start, int end) {
		int selected = 0;
		for (int i = start - 1; i < end; i++) {
			if (res[i] == 0) {
				res[i] = idx + 1;
				selected++;
			}
		}

		if (selected > temp) {
			temp = selected;
			ans = idx + 1;
		}
	}// chk

}// class-end