https://www.acmicpc.net/problem/1637
1637번: 날카로운 눈
첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미
www.acmicpc.net
정수더미 속에서 홀수 개 존재하는 정수를 찾으면 되는 문제입니다.
예제 입력을 보면 A C B 가 차례로
1 10 1
4 4 1
1 5 1
6 10 1
이 있습니다.
나오는 정수들을 살펴보면
1 2 3 4 5 6 7 8 9 10
4
1 2 3 4 5
6 7 8 9 10
정수더미는 위와 같이 있습니다.
이 정수더미를 1 이하의 수의 개수, 2 이하의 수의 개수, ..... 10 이하의 개수를 나타내보겠습니다.
1 2 3 4 5 6 7 8 9 10
2 4 6 9 11 13 15 17 19 21
규칙이 좀 보이시나요???
중간에 홀수 개의 정수가 있으면 그 이후에는 모두 홀수 개가 나오게 됩니다.
그렇다면 이진탐색 파라메트릭 서치를 이용할 수 있게 됩니다.
이진탐색으로 홀수인 것 중에 가장 왼쪽인 것을 찾아주면 홀 수 개의 정수를 찾을 수 있게 됩니다.
파라메트릭 서치를 모르신다면 한 번 검색하셔서 익히신 뒤 문제를 다시 봐보시는 것을 추천드립니다.
public static int[][] arr;
public static boolean check(long num){
long total = 0;
for(int i = 0; i < arr.length; i++){
long n = Math.min(arr[i][1], num);
if(n >= arr[i][0]) {
total += 1 + (n - arr[i][0]) / arr[i][2];
}
}
return total % 2 == 1;
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr = new int[N][3];
for(int i = 0; i < N; i++){
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
arr[i][2] = Integer.parseInt(st.nextToken());
}
long s = 1;
long e = Integer.MAX_VALUE;
long ans = 0;
while(s <= e){
long mid = (s + e) / 2;
if(check(mid)){
ans = mid;
e = mid - 1;
}else{
s = mid + 1;
}
}
int count = 0;
for(int i = 0; i < arr.length; i++){
if(ans <= arr[i][1] && ans >= arr[i][0]){
if((ans - arr[i][0]) % arr[i][2] == 0){
count++;
}
}
}
if(count % 2 == 0){
System.out.println("NOTHING");
return;
}
System.out.println(ans + " " + count);
'백준 > 자바' 카테고리의 다른 글
백준 자바 14247 나무 자르기 (0) | 2022.05.10 |
---|---|
백준 15736 자바 청기 백기 (72ms 가장 빠른 코드!) (0) | 2022.02.24 |
백준 자바 2775번 일차원 배열만 사용하여 메모리 줄이기 (0) | 2022.01.26 |