문제 이해
A C B가 여러 줄 주어질 것이다.
우리는 A C B를 통해 아래와 같은 수들을 만들 수 있다.
A, A+B, A+2B, A+3B, ... , A+kB, ...
이렇게 수들을 만들다가 A+tB > C가 되는 순간 멈춘다.
즉, A+tB일 때 처음으로 C보다 커졌다면, A, A+B, A+2B, ..., A+(t-1)B까지 수를 만들 수 있을 것이다.
A,C,B는 여러 줄 주어지므로 우리가 만들 수 있는 수들은 매우 다양할 것이다.
그런데, 이렇게 만든 수는 특징이 있다.
1개의 정수는 홀수개 존재하고 나머지 정수는 모두 짝수개 존재하는 것이다.
이 때 홀수 개 존재하는 단 1개의 정수를 출력하는 것이 문제이다.
문제 풀이
문제 해결을 위한 개념을 찾으면 매우 쉽게 풀리는 문제이다.
하지만 그 개념 찾기가 생각보다 까다로운데, 수학적 특성을 이용하는 문제이기 때문이다.
"짝수 + 홀수 = 홀수, 짝수 + 짝수 = 짝수"
내가 임의의 수 K를 지정하고, K보다 작은 숫자가 몇 개 존재하는지 파악해볼 것이다.
만약 K 이하의 숫자가 홀수일 경우 홀수개 존재하는 1개의 정수는 K이하일 것이다.
반대로 K 이하의 숫자가 짝수인 경우 홀수개 존재하는 1개의 정수는 K보다 클 것이다.
위 특성을 이용한 문제 풀이 방법을 생각해보자.
-
임의의 수 K를 지정하자. 이 때 K의 범위는 1이상이다. 그렇다면 최대값은 무엇일까?
내가 (A,C,B) 쌍으로 만들 수 있는 최대값은 C일 것이다. 즉, 여러 개의 (A,C,B) 쌍 중 최대 C값을 찾으면 그 때의 C값이 K의 최댓값이 될 것이다. -
K 이하인 값의 개수는 몇개일까?
우리는 (A,C,B)로 A, A+B, ... , A+kB, ...로 만들 수 있다. 여기서 A를 빼보자
이 경우 0, B, ..., kB, ...로 B의 배수가 될 것이다.
즉, 한 개의 (A,C,B) 쌍에서 K 이하인 수는 (K-A) / B개 존재할 것이다!
라고 생각하면 틀린다.
kB에서 k는 0부터 시작하기 때문에 { (K-A) / B } + 1개 존재한다.
- 참고로 K-A < 0가 될 가능성도 있으니, 이 경우를 따로 처리해 줘야 한다.
- K 이하인 값이 홀수 개 존재
내가 찾는 값은 K 이하이다. 따라서 답이 될 가능성이 존재한다. 또한 K "이하"에 존재하므로 K 크기를 낮춰서 재확인해야하므로 right를 변경시킨다
K 이하인 값이 짝수 개 존재
내가 찾는 값은 K 초과이다. 따라서 답이 될 가능성이 없다.
또한 K "초과"이므로 K 크기를 높여서 재확인해야하므로 left를 변경시킨다.
참고로, 이 문제의 경우 홀수개 존재하는 정수가 없는 경우가 생길 수도 있다. 따라서 초기값을 절대로 나올 수 없는 수(예를 들어 -1)로 설정하고, 만약 정답이 처음 설정한 값과 동일하다면 "NOTHING"을 출력하는 로직을 추가해줘야 한다.
또한, 홀수 개 존재하는 특정 정수가 몇 개 존재하는지도 확인해봐야하는데, 물론 더 효율적인 방법이 존재하지만 간단하게 특정 정수가 T일 경우 (T 이하인 정수 개수) - (T-1 이하인 정수 개수)를 통해 정확히 T인 정수 개수를 구했다.
코드
import java.io.*;
import java.util.*;
class Value{
int A;
int C;
int B;
public Value(int A, int C, int B) {
this.A = A;
this.C = C;
this.B = B;
}
}
public class Main {
static int N;
static Value[] values;
static Long determination(long value) {
// value 이하의 정수가 몇 개 존재하는지 계산하는 메서드
long sum = 0;
for(int i =0;i<N;i++) {
long X = Math.min(value, values[i].C);
// value가 (A,C,B) 쌍 중 C보다 작다면 C까지 Search할 경우
// 더 많은 수를 Search하게 된다
// 따라서 둘 중 작은 값까지 Search하게 하기 위한 장치이다.
X = X -values[i].A;
if(X < 0) {
continue;
}
// 아래 3번째 틀렸습니다 확인
long k = X/values[i].B + 1;
sum+=k;
}
return sum;
}
static void bin_search(Long right) {
Long left = (long) 1;
long mid;
Long ans = (long) -1;
// 홀수 개 존재하는 수가 있다면 무조건 ans는 양수.
while(left<=right) {
mid = ((long) (left+right))/2;
Long count = determination(mid);
if(count%2!=0) {
ans = mid;
right = mid - 1;
}else {
left = mid + 1;
}
}
if(ans==-1) {
System.out.println("NOTHING");
return;
}
System.out.println(ans+" "+
(determination(ans)-determination(ans-1)));
}
public static void main(String[] args) {
FastReader sc = new FastReader();
N = sc.nextInt();
values = new Value[N];
long max = -1;
int A, C, B;
for(int i =0;i<N;i++) {
A = sc.nextInt();
C = sc.nextInt();
B = sc.nextInt();
values[i] = new Value(A,C,B);
max = Math.max(max, C);
}
bin_search(max); // max : C중의 최댓값. 이분 탐색 범위 중 최댓값
}
static class FastReader // 빠른 입력을 위한 클래스
}결과
- 4번째 틀렸습니다 : value보다 작은 개수의 최댓값은 Int형 범위를 넘어선다. 즉, determination()의 return 값은 long이여야 하는데 int형으로 반환하여 틀렸다.
- 3번째 틀렸습니다 : 설명하지 않았지만 매우 중요한 코드가 있다.
X = X -values[i].A;
if(X < 0) {
continue;
}바로 이부분이다.
만약, X - values[i].A가 음수라면, Search할 필요가 없다.
이는 어떤 상황이냐면, 나는 3 이하인 값을 찾고 싶은데 (A,C,B) 쌍을 통해 만들어진 숫자는 4, 6, 8, ...인 상황이다. 즉, 3 - 4= -1이고, 당연히 0개 이기 때문에 계산을 수행하면 안된다. 그런데 3번째 틀렸습니다 때는 이 부분을 간과했다. 따라서 위 부분을 추가시켜줌으로써 계산을 생략해야 하는 (A,C,B) 쌍에 대한 처리를 수행해주었다.
