인프런 커뮤니티 질문&답변

이문제는 카카오 2019년 1차 테스트 4번 문제인 "무지의 먹방 라이브" 문제와 동일 문제입니다. "음식"을 "작업"으로 말을 바꾼것 외에는 다른게 없습니다. 이 강좌에서 N제한(N=2,000, K=2000,000)은 카카오에서 제시한 정확성 테스트 N제한입니다. 제가 드린 소스코드(단순반복문으로 해결)로도 타임 리밋없이 나와야 정상입니다. 제가 준 소스코드를 a배열의 크기를 넉넉히 int a[3000]정도로 잡고 다시 채점받아보기시 바랍니다. 그래도 타임리밋이 난다면 채점하는 컴퓨터의 성능문제라 생각됩니다.

사실 후속강좌를 모의고사 형태로 만들려고 문제를 선별하고 있는데,  몇 일전 이 문제를 카카오에서 효율성 테스트로 제시한 N제한인 N=200,000과 K=2*10^13으로 문제를 만들어 모의고사 1회 2번 문제로 정하고 풀어봤습니다. 

이 문제를 나누기 연산으로 수학적으로 접근하려고 시도한 것 자체가 대단한 것입니다. 차후에 굉장한 실력자가 될 것 같습니다.

다음은 카카오 블로그에서 제시한 무지의 먹방라이브 문제 해설입니다. 음식을 작업으로 생각하고, 음식을 다 먹는 시간을 작업을 다 처리하는 시간으로 생각하면 됩니다.

먼저 아래 풀이법을 보시고 스스로 코드를 짜보시기 바랍니다. 그래도 안되시면 아래에 카카오 해설을 기반으로 제가 짠 코드가 있습니다.  스스로 분석해보시기 바랍니다. 

문제 풀이

이 문제를 완전히 해결하려면 효율성 테스트를 통과해야 합니다.
효율성 테스트의 제한 사항은 정확성 테스트보다 까다롭기 때문에 정확성 테스트를 통과한 풀이를 그대로 적용하면 시간 초과가 발생합니다. 따라서, 실행 시간을 줄일 수 있는 아이디어가 필요합니다.

정확성 풀이

시간이 1초 지날 때마다 다음 먹을 음식을 반복문을 이용해 하나하나 찾아가며 시뮬레이션하면 됩니다.

효율성 풀이

먼저 음식별 필요 시간을 오름차순으로 정렬합니다. 시간의 오름차순으로 정렬해두면 음식을 먹는 데 소요되는 시간을 한꺼번에 지울 수 있습니다. 예를 들어 정렬한 시간이 T = [1, 3, 3, 4, 5]라면 처음에 T[0] * 5 = 5만큼의 시간을 한꺼번에 지울 수 있습니다. 다음으로 T[1]부터 남은 시간을 한꺼번에 제거합니다. 즉, (T[1] – T[0]) * 4 = 8 만큼의 시간을 한꺼번에 지웁니다. 마찬가지로 (T[2] – T[1]) * 3 = 0 만큼의 시간을 한꺼번에 지울 수 있습니다.

위와 같은 방법으로 시간을 지워가다가, 지운 시간의 합이 K 보다 커지게 되면 남은 시간의 개수로 나눈 나머지를 이용해 K 초 후 다시 먹기 시작해야 될 음식의 번호를 바로 구할 수 있습니다. 이때, 남은 시간을 다시 원래 음식의 번호 순서대로 재정렬해야 합니다.

꼭 이 방법이 아니라도 K에 도달하는 시점을 빠르게 구할 수만 있으면 실행 시간을 줄일 수 있습니다.

(소스코드) 저는 정렬을 처음에 한 번만 하고 답을 찾을 때는 O(n)으로 반복문을 돌렸습니다.

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 200005;
int n;
long long T[MAX_N];
long long SortT[MAX_N];
long long k;

int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);
	cin>>n;
	for(int i=1; i<=n; i++) cin>>T[i];
	cin>>k;
	for(int i=1; i<=n; i++) SortT[i] = T[i];
	sort(SortT+1, SortT+n+1);
	long long rest = n, lastT = 0;
	for(int i=1; i<=n; i++) {
		long long nowT = SortT[i];
		if(k < (rest * (nowT - lastT))) {
			int index = k % rest;
			int cnt = 0;
			for(int j=1; j<=n; j++) if(T[j] >= SortT[i]) {
				if(cnt == index) {
					cout<<j;
					return 0;
				}
				cnt++;
			}
		}else{
			k -= (rest * (nowT - lastT));
		}	
		lastT = SortT[i];
		rest--;
	}
	cout<<"-1";
	return 0;
}

추신) 위 코드처럼 include를 사용하려면 Dev-C++의 컴파일러를 아래 그림처럼 업그레드 해야 합니다. 

도구-컴파일러 설정에서 컴파일러 추가 명령을 체크하시고, "-std=c++14" 써넣으시면 됩니다.