4번 문제는 효율성 테스트와 정확성 테스트의 2가지 영역으로 나눈 테스트입니다.
따라서 2가지로 나누어 풀어보도록 하겠습니다.
1) 정확성
정확성의 경우 k의 범위가 200만이므로 정말로 하나씩 다 먹어보면서, 음식의 개수가 0이 되면 사라지는 방식으로 다음에 먹어야 할 음식이 무엇인지 알 수 있습니다.
2) 효율성
효율성 테스트는 k의 범위가 $10^{13}$ 을 넘어가므로 모두 해볼 수 없습니다. 따라서, 이번에는 다른 방법으로 생각을 해봐야 합니다. 모든 경우를 다 해보는 것이 아니라, 어떤 특정 음식을 다 먹었을 때, 그 음식을 다 먹기까지 걸리는 개수를 구해보는 것입니다.
예를 들어
5 | 4 | 7 | 2 | 4 |
로 음식이 배치 되어있다고 하면, 가장 먼저 다 먹게 되는 음식은 바로 4번이며, 다 먹는 시점은 9초입니다. 이걸 조금 다르게 표현을 하면, "적어도 음식의 개수(5) * 음식의 양(2) 인 10초 이내에는 4번 음식을 다 먹을 수 있다" 라고 표현할 수 있습니다. 이렇게 표현하게 되면, 이제 k가 10보다 같거나 작다면 이 범위 내에서 나머지 연산을 통해 어떤 음식을 먹는지 $O(1)$에 알 수 있습니다.
이제 4번 음식을 다 먹으면 남은 음식은 4개이고, 2번 음식과 5번 음식이 그 다음으로 다 먹게 될 음식이 됩니다. 이 때, 위에서 표현했던 원리로 "2번 음식은 적어도 8초 이내에는 다 먹을 수 있다" + 10 = "2번 음식은 적어도 18초 이내에는 다 먹을 수 있다" 가 됩니다. 이런 식으로 모든 경우를 다 해 볼 필요 없이, 음식의 개수가 0이 되어 사라지는 경우를 분기로 하여, 그 범위 내에 k가 포함이 될 경우를 찾은 다음 나머지 연산을 통해 해결할 수 있습니다.
음식의 개수가 적은 것부터 확인을 해야 하므로, 정렬이 필요합니다. 그 다음 음식의 개수만큼 돌며 확인합니다. 따라서 음식의 개수 $N$에 대해 $O(NlogN)$ 으로 풀 수 있습니다.
소스코드는 효율성 테스트 코드만 올립니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;
class Node {
public:
ll no, amount;
Node() {}
Node(ll n, ll a) {
no = n, amount = a;
}
bool operator <(const Node &n) const {
return amount == n.amount ? no < n.no : amount < n.amount;
}
} v[200011];
bool cmp(Node &a, Node &b) {
return a.no < b.no;
}
int solution(vector<int> t, long long k) {
ll sum = 0;
v[0] = { 0,0 };
for (int i = 1; i <= t.size(); i++) {
v[i] = { i, t[i - 1] };
sum += t[i - 1];
}
if (sum <= k) return -1;
sort(v + 1, v + t.size() + 1);
for (int i = 1; i <= t.size(); i++) {
ll time = (v[i].amount - v[i - 1].amount) * (t.size() - i + 1);
if (k <= time) {
sort(v + i, v + t.size() + 1, cmp);
k %= (t.size() - i + 1);
k += i;
return v[k].no;
}
k -= time;
}
return -1;
}