문제링크)
https://www.acmicpc.net/problem/15732
입력
첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 넣는 규칙을 뜻한다. D는 모든 규칙으로 넣을 수 있는 도토리의 수보다 같거나 작다.
출력
D개의 도토리를 규칙에 맞게 상자 앞에서부터 넣었을 때 마지막 도토리가 들어가는 상자의 번호를 출력하시오.
문제 풀이
문제 이해
문제가 조금 해석하기 어려울 수 있지만, 쉽게 설명하자면 다음과 같다.
상자 모두에 넣을 필요가 없이 규칙으로 명시된 상자들에만 도토리를 하나씩 넣는다.
그리고 끝까지 갔다면 남은 도토리를 가지고 맨 처음(1번)부터 다시 하나씩 넣어간다.
이렇게 넣어갈 때, 마지막으로 도토리를 넣게된 상자의 번호를 출력한다.
1.무식하게 접근하기
무식한 방법으로 풀어보자면, 각 상자의 번호를 표시해두고 1번부터 끝까지 순회하면서 도토리를 넣어보는 방법이 있다.
우선, 도토리가 최대 10억개나 될 수 있으므로 정석적인 방법을 도입해볼 필요가 있다.
1부터 N번까지 넣게되는 도토리 수를 계산한 뒤, 이로 D를 나눈 나머지로 연산을 하면 필요없는 계산을 줄일 수 있다.
그러나 핵심적인 문제는 D를 줄이는 것이 아니라 최대 100만개나 되는 상자들에 대해서 최대 10000개인 규칙에 따라 도토리를 넣는 상자를 찾는 것에 있다.
몇 번 상자에 도토리를 넣어야 할지는 바로 알 수 없다.
결국 도토리 넣을 상자를 알려면 모든 규칙에 대해 시작점부터 끝점까지 간격마다 방문해봐야 한다.
그런데 모든 규칙이 1번부터 100만번까지 1개 간격으로 돌아간다고 하면 최대 연산 횟수는 이 되므로 시간안에 수행하기가 어렵다.
2. 도토리 넣는 연산을 빠르게.
A부터 B까지 특정 규칙을 적용했을 때, 몇 개의 도토리를 넣을 수 있는지 계산하는 것은 쉽다.
이 공식은 D를 작게 만드는 연산에서 이미 한 번 사용해야 한다.
반면, 위 식을 이용하면 특정 구간 1, B에 대해 어떤 규칙으로 도토리를 넣을 때 마지막으로 넣게 되는 상자 번호를 쉽게 계산할 수 있다.
주의할 점은 시작점은 규칙마다 다르고, 종료점은 원하는 종료 지점과 규칙 종료 지점 중 작은 값이다. 또한, 종료점은 시작점보다 같거나 커야 한다. 그렇지 않다면 도토리는 0개 넣을 수 있다.
특정 지점에 대해 가장 마지막에 도토리를 넣게되는 상자 번호는 위 공식을 응용하여 계산하며 그 값은 모든 규칙에 대해 위 공식 적용시 가장 큰 인덱스가 된다.
이제 시간복잡도로 마지막 상자 번호를 찾을 수 있게 되었다.
그러나, 정확히 어디가 적절한 상자인지 알 수 없는 상황이다. 따라서 1번부터 N번까지 위 공식들을 적용해보면서 D개의 도토리를 넣을 수 있는 상자 위치를 찾아나가야 하는데,
이러면 결국 번의 연산이 필요하게 된다.
3. 도토리 넣는 구간을 찾는 방법
1번 상자부터 A < B < C인 상자번호 A, B, C에 대해서 도토리를 넣는다고 할 때,
A에 가장 적은 도토리, 그 다음은 B, C 순으로 많아진다.
이 성질은 모든 상자에 대해서 성립하기 때문에 논리적으로는 정렬상태로 볼 수 있다.
임의의 상자 A를 짚었을 때, 1번부터 A까지 넣을 수 있는 도토리 양이 D보다 작다면, A부터 N 사이에 정답이 존재한다.
반대면 1부터 A사이에 정답이 존재하므로 범위를 좁혀 탐색할 수 있다.
따라서, 이진 탐색을 적용하여 빠르게 탐색이 가능하다.
결과적으로 최대 연산은
번이 된다.
프로그램 구현
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tokens;
tokens = br.readLine().split(" ");
int N = Integer.parseInt(tokens[0]), K = Integer.parseInt(tokens[1]); long D = Long.parseLong(tokens[2]);
int[][] rules = new int[K][3];
long totalInACycle = 0;
// 1부터 N까지 모두 합쳐 몇개의 도토리를 넣을 수 있는지 계산 -> 쉬움. O(1)
for(int i = 0; i < K; i++) {
tokens = br.readLine().split(" ");
rules[i][0] = Integer.parseInt(tokens[0]);
rules[i][1] = Integer.parseInt(tokens[1]);
rules[i][2] = Integer.parseInt(tokens[2]);
totalInACycle += getPossibleCount(rules[i][0], rules[i][1], rules[i][2]);
}
//10억개나 되는 도토리 -> 쉽게 하려면 나머지 연산을 써서 수를 줄여야 함.
D %= totalInACycle;
if(D == 0) {
D = totalInACycle;
}
int left = 0, right = N;
while(left < right) {
int mid = (left + right) / 2 + 1;
long partialSum = 0;
for(int[] rule : rules) {
partialSum += getPossibleCount(rule[0], Math.min(mid, rule[1]), rule[2]);
}
if (partialSum >= D) {
right = mid - 1;
} else {
left = mid;
}
}
System.out.println(right + 1);
}
public static long getPossibleCount(int start, int end, int term) {
if(end < start) return 0;
return (end - start) / term + 1;
}
}
/*
A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 더 넣는 규칙
이러한 규칙들을 K개
첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다.
그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 넣는 규칙을 뜻한다.
D는 모든 규칙으로 넣을 수 있는 도토리의 수보다 같거나 작다.
100번 상자부터 150번상자까지 10개 간격으로, 110번 상자부터 150번 상자까지 15개 간격으로 넣는다면
100 110 120
110 125
10억개나 되는 도토리 -> 쉽게 하려면 나머지 연산을 써서 수를 줄여야 함.
1부터 N까지 모두 합쳐 몇개의 도토리를 넣을 수 있는지 계산 -> 쉬움. O(1)
100만개의 상자에 K개의 규칙대로 하나하나씩 숫자를 찍어보는 것은 어려움 O(K*N)
10의 6제곱 ~~ 2의 20제곱.
20 * 1000000 * 10000
이 연산을 빠르게..
-> 이진탐색한 위치를 T라고 할때, 1~T까지 몇개 들어있는지 구하는것도 빠르게 할 수 있다.
T가 일치할 때, (정답케이스. D가 0으로 떨어질 때)
T보다 작고 제일 큰 상자를 찾으면 됨.
200 2 14
100 150 10
110 150 15
100 1 100
1 100 1
*/
