[백준 Java] 1637번 날카로운 눈

💡문제

🌟[Platinum IV]🌟 날카로운 눈 - 1637

문제 링크

성능 요약

메모리: 21656 KB, 시간: 244 ms

---

🤔접근법

주어진 N개의 정수 더미를 하나의 더미로 만들었을 때 홀수개의 개수를 가지는 정수와 개수를 출력

범위 체크 및 시간복잡도 예상

• 1 ≤ N ≤ 20,000
• 2,147,483,647 ≤ A, B, C ≤ 2,147,483,647 (21억)
• A + kB ≤ C

풀이법

❌ 접근 방법. 완탐

1. 각각의 정수 더미를 배열로 생성한다. → $O(21억 * N)$
2. 1 ~ 21억까지 탐색하면서 각 정수 더미에서 몇개씩 들어있는지 구한 후 합산한다. → $O(21억 * N)$
3. 개수가 홀수 개 인지 판단한다.
4. 홀수개인 정수가 없다면 NOTHING을 출력한다.

➡️ 해당 풀이법의 시간 복잡도 : $O(21억 * N)$ → 시간 초과

⭕ 접근 방법. 이분탐색 + 매개변수 탐색

A = 1 , C = 21억, B = 1 인 경우 21억 만큼 탐색하게 되어 시간 초과가 나는걸 최적화 해서 줄여야 한다.

이분탐색 공부하면서 이분탐색일 가능성이 높은 문제를 알게되었다.

문제에서 수열을 만드는 규칙이 주어진다. → 근데 직접 만들 수는 없음
그리고 특정 위치에 대한 수열의 정보를 구하라.
⇒ 매개변수 탐색을 이용

날카로운 눈 문제도 A 부터 C까지 +B 씩 증가하는 규칙이 있는 수열이다.

다만 C가 21억까지 가능하기 때문에 직접 만들 수는 없다.

그렇다면 어떤값이 매개변수로 주어졌을 때 홀수 인지 짝수인지 판별하면 될 것 같았다.

또한 이분 탐색을 사용하려면 단조성을 가지고 있어야 생각했다

단조성은 ooooooxxxx 거나 xxxxoooo 인경우 를 말한다. ooxxxooxxx 는 안됨

홀수와 짝수의 판별은 2로 나눈 나머지로 생각했으며

홀수개를 가지는 정수는 정수보다 같거나 작은 수들의 개수를 2로 나눴을때 1이 된다.

그 이유는 예시로 보자

1 1 2 2 2 2 3 3 4 4 5 5 5 6 6 7 7

이라고 할때 정수 5가 홀수개를 가진다.

이걸 홀짝으로 표현하면

1	2	3	4	5	6	7
짝	짝	짝	짝	홀	짝	짝

그렇다면 정수 5보다 작거나 같은 정수들의 개수도 홀수이다.

그 이유는 짝수 + 짝수 + 홀수 는 홀수이기 때문이다.

그럼 홀수 + 짝수는 홀수라는 걸 알 수 있고 홀수 + 짝수 + 짝수도 홀수라는 걸 알 수 있다.

그렇다면 6보다 작거나 같은 수는 홀수를 무조건 포함하고 있으므로 홀수이고

7역시도 마찬가지다.

1	2	3	4	5	6	7
짝	짝	짝	짝	홀	홀	홀

그렇다면 위와 같은 표로 바꿀수 있다.

첫번째 표는 정수의 개수를 홀짝으로 나눈거고

두번째 표는 정수와 작거나 같은 수의 개수를 홀짝으로 나눈 것이라는 차이가 있다.

이렇게 되면 이분 탐색을 통해 작거나 같은 수의 개수가 홀인 것들 중 가장 작은 수를 찾으면 되니까

이분탐색의 lower Bound를 활용하여 구할 수 있다. (가장 왼쪽)

자 그러면 여기서 문제는

정수의 작거나 같은 정수들의 개수를 어떻게 구하느냐 이다.

이것도 예제로 알아보자

A = 37, C = 60, B = 4

37부터 60까지 +4 씩 한 수열을 써보면 아래와 같다.

37	41	45	49	53	57

여기서 우리는 50보다 작거나 같은 수의 개수를 구할 것이다.

우선 숫자들이 어떻게 구해졌는지 보면

37 = A + 0B = 37 + 0

41 = A + 1B = 37 + 1*4

45 = A + 2B = 37 + 2*4

49 = A + 3B = 37 + 3*4

53 = A + 4B = 37 + 4*4

57 = A + 5B = 37 + 5*4

공통적으로 37이 들어가 있음을 확인할 수 있다.

그럼 37을 모두 빼보자.

37	41	45	49	53	57
0	4	8	12	16	20

4단 곱셈으로 변하게 된다.

그렇다면 우리가 구하려는 50에서 37을 빼면

13이 되고

우리는 4단 곱셈에서 13보다 작거나 같은 수를 구하면 되는 문제로 바꼈다.

이는 13 / 4 + 1을 하면 된다. +1을 하는 경우는 첫번째 숫자 37 즉 A을 빼면 0이 되는 숫자가 항상 있기 때문이다.

이를 정리해보면 작거나 같은 값의 개수를 구하려는 정수를 x라고 하면

(x - A) / B +1 라고 정리 할 수 있다.

추가로

x의 정수와 같은 수들의 개수를 구하고 싶다면 어떻게 하면 될까 ?

x보다 작거나 같은수 - (x-1)보다 작거나 같은 수를 계산하면 된다

1. 1(start) ~ 21억(end)까지 이분탐색하여 mid를 홀수개를 가지고 있는지 알아볼 정수 x로 선택→ O(log21억)
2. 각 정수 더미를 탐색하면서 정수 하나 더미에서 x보다 작거나 같은 정수의 개수를 구해 그것의 합계를 구한다. → O(N)
3. 그 합계를 2로 나눴을때 나머지가 1이면 홀수라는 의미니까 end 를 mid -1로 구간 수정
4. 나머지가 0이라면 짝수라는 의미니까 start = mid +1 로 구간 수정

➡️ 해당 풀이법의 시간 복잡도 : $O(Nlog21억)$

---

😎SUCCESS

고냥 담박에 성공!

플레티넘 원샷원킬하는 영광의 순간!

---

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;           // 더미의 개수
    static Dummy[] dummies; // 더미 객체 배열

    // 더미 클래스 정의
    static class Dummy {
        long a;  // 시작 정수
        long b;  // 정수 간격
        long c;  // 마지막 정수

        // 생성자
        public Dummy(long a, long c, long b) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        // 디버깅을 위한 toString 메소드 오버라이드
        @Override
        public String toString() {
            return "Dummy{" +
                    "a=" + a +
                    ", b=" + b +
                    ", c=" + c +
                    '}';
        }
    }

    static long max = Long.MIN_VALUE; // 더미 배열 내 최대 c값 저장

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dummies = new Dummy[N];

        // 더미 객체 배열 초기화 및 입력 받기
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            dummies[i] = new Dummy(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));
            max = Math.max(max, dummies[i].c); // 최대 c값 갱신
        }

        long start = 1;       // 이분 탐색 시작값
        long end = max;       // 이분 탐색 끝값
        long resultNum = -1;  // 결과로 찾은 홀수개 존재하는 정수

        // 이분 탐색 실행
        while (start <= end) {
            long mid = (start + end) / 2;
            long numCnt = getSmallOrEqualNumCnt(mid);

            // 홀수개 존재하는 정수 찾은 경우
            if (numCnt % 2L == 1) {
                end = mid - 1;
                resultNum = mid;
            } else {
                start = mid + 1;
            }
        }

        // 결과가 없는 경우 "NOTHING" 출력 후 종료
        if (resultNum == -1) {
            System.out.println("NOTHING");
            return;
        }

        // 홀수개 존재하는 정수의 개수 계산
        long cnt = getSmallOrEqualNumCnt(resultNum) - getSmallOrEqualNumCnt(resultNum - 1);

        // 결과 출력
        System.out.println(resultNum + " " + cnt);
    }

    // target보다 작거나 같은 숫자의 개수를 반환하는 메소드
    private static long getSmallOrEqualNumCnt(long target) {
        long total = 0;

        // 모든 더미에 대해 처리
        for (int i = 0; i < N; i++) {
            // target보다 작은 경우 무시
            if (target < dummies[i].a) continue;

            // 더미의 c값이 target보다 작은 경우
            if (dummies[i].c < target) {
                // 해당 더미에서 target 이하의 숫자의 개수를 더함
                total += getCnt(dummies[i].c, i);
            } else {
                // 그렇지 않으면 해당 더미에서 target 이하의 숫자의 개수를 더함
                total += getCnt(target, i);
            }
        }

        return total;
    }

    // target 이하의 숫자의 개수를 반환하는 메소드
    private static long getCnt(long target, int i) {
        return ((target - dummies[i].a) / dummies[i].b) + 1;
    }
}