[BOJ] 백준 #3985. 롤 케이크

🎨 문제

문제 링크: https://www.acmicpc.net/problem/3985

• 알고리즘 분류: 구현
• 난이도: Bronze 1

길이 L미터 짜리 롤케이크를 방청객 N명에게 나눠주려고 한다.

1번부터 N번까지의 방청객들은 차례대로 각각 원하는 조각을 범위 조각P부터~조각K까지 가져간다.

이때 이미 가져간 조각은 뒷사람이 원하더라도 받지 못한다.

가장 많은 조각을 원했던 방청객의 번호, 실제로 가장 많은 조각을 가져간 방청객의 번호를 구하는 문제다.

단, 답이 여러 개인 경우에는 번호가 작은 사람을 출력한다.

 

 

💬 풀이

 

 

 

 

👩‍💻 코드

C++

#include <iostream>
#include <algorithm>
using namespace std;

int cake[1001]; // 케이크 조각 별로 방청객 번호
int cnt[1001]; // 방청객 번호 별로 실제 받게되는 케이크 수 

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int L, N;
	cin >> L >> N;
	int st, en, _max=-1, _max_index=-1;
	for (int i = 1; i <= N; i++) {
		cin >> st >> en;
		for (int j = st; j <= en; j++) {
			if (cake[j] == 0) { // 케이크 배열이 비어있는 경우에만 갱신
				cake[j] = i;
			}
		}

		if (en-st+1 > _max) { // _max를 초과 시 _max_index 갱신
			_max = en-st+1;
			_max_index = i;
		}
	}
	cout << _max_index << '\n';


	for (int i = 1; i <= L; i++) {
		if (cake[i] > 0) cnt[cake[i]]++; // 방청객 별로 실제 받게되는 케이크 수 카운트
	}

	_max=-1, _max_index=-1;
	for (int i = 1; i <= N; i++) { // _max를 초과 시 _max_index 갱신
		if (cnt[i] > _max) {
			_max = cnt[i];
			_max_index = i;
		}
	}
	cout << _max_index << '\n';

	return 0;
}