문제 링크

성능 요약

메모리: 23916 KB, 시간: 308 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2025년 2월 18일 23:52:44

문제 설명

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어볼 수 있는 날카로운 눈을 가진 기이한 원숭이였다. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다.

어느 날 멍멍이는 원숭이의 날카로운 눈이 너무 샘나서 원숭이를 직접 패고 싶었지만 날카로운 눈으로 찌를까봐 무서워서 때리지는 못하고 대신, 원숭이에게 문제 하나를 던져주었다. 그 문제는 다음과 같다.

정수가 여러 개 모여 있는 정수더미가 있다. 그 안에 어떤 특정한 정수 하나만 홀수개 존재하고 나머지 정수는 모두 짝수개 존재한다. 정수더미 속에서 날카로운 눈을 이용해 홀수개 존재하는 정수를 찾아야 하는 문제이다.

근데 멍멍이가 문제를 전달해 주려다가 생각해보니 정수더미 안에 정수가 적게 있으면 문제가 너무 쉬워지게 되는 것이다. 그래서 정수더미안에 정수를 무지막지하게 많이 넣기로 했다. 정수더미가 주어졌을 때, 그 안에 홀수개 존재하는 정수를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 안에 있다는 것을 나타낸다. A, B, C는 1보다 크거나 같고 2,147,483,647보다 작거나 같은 정수이다. 정수더미는 N개의 입력이 나타내는 정수들을 모두 포함한다.

출력

첫째 줄에 정수 두 개를 출력하는데, 첫 번째는 홀수개 존재하는 정수를 출력하고, 두 번째는 그 정수가 몇 개 들어있는지 출력한다. 만약 홀수개 존재하는 정수가 없다면 NOTHING을 출력한다.

풀이

느낀점

• answer 초기화 위치를 잘못 잡아서 정수 더미의 수가 연속된 2개의 숫자뿐일 때의 경우를 고려하지 못했다. 디버깅 지옥ㅠ

설계 : 30분

• 매개변수 이분탐색: mid를 기준으로 두 파트로 나뉜 정수의 전체 개수를 세어 홀수인 쪽으로 범위를 좁혀간다.
• 처음 시작시 전체 개수가 짝수이면 홀수개인 정수가 없으므로 NOTHING을 출력한다.
• 두 파트의 정수의 개수는 유효한 구간을 순회하며 (high - low) / B + 1; 를 계속 더하면 각 조건에 맞는 정수 개수를 구할 수 있다.
  • 단, high - low가 음수일때는 통과한다.

코드(Java)

• 구현 시간: 120분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 날카로운 눈_1637
 * Date: 2025.02.18
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static int[][] condition;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
        condition = new int[n][];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            condition[i] = new int[] {a, c, b};
            min = Math.min(min, a);
            max = Math.max(max, c);
        }

        long low = min;
        long high = max;
        long mid;

        long answer = getRangeCount(low, high);
        if (answer % 2 == 0) {
            bw.write("NOTHING");

        } else {
            while (low < high) {
                mid = (low + high) / 2;

                long cnt = getRangeCount(low, mid);
                if (cnt % 2 == 0) {
                    answer -= cnt;
                    low = mid + 1;
                } else {
                    answer = cnt;
                    high = mid;
                }
            }

            bw.write(String.valueOf(low) + " " + String.valueOf(answer));
        }

		bw.flush();
		bw.close();
		br.close();
	}

    public static long getRangeCount(long min, long max) {

        long sum = 0;
        for (int[] cond : condition) {
            long low = Math.max(min, cond[0]);
            long gap = (low - cond[0]) % cond[2];
            if (gap != 0) low += cond[2] - gap;

            long high = Math.min(max, cond[1]);

            if (high - low >= 0) {
                long cnt = (high - low) / cond[2] + 1;

                sum += cnt;
            }
        }

        return sum;
    }

}