[백준] 12779번 - 상품 is 뭔들 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 $a$, $b$ 에 대해 $a$ 초과 $b$ 이하인 구간에서 약수의 개수가 홀수인 수의 개수를 구하고 이를 구간의 크기로 나눈 후 기약 분수로 출력해야 하는 문제다. 약수의 개수는 짝을 이뤄서 나오게 되는데 완전제곱수의 경우는 자기 자신과 짝이 되는 약수가 존재해서 약수의 개수가 홀수가 됨을 활용해야 하며 기약 분수로 나타내기 위해서는 분자와 분모의 최대공약수로 나눠야 하는데 이를 위해 유클리드 호제법을 활용했다.

주어진 구간에서 완전제곱수의 개수를 찾는 방법은 이분 탐색 + 매개 변수 탐색을 활용한 방식을 적용했다. 이분 탐색의 경우 $n \times n$ 이 $a$ 초과 $b$ 이하인 $n$ 의 범위를 구했는데, Upper Bound로 $n \times n > b$ 인 $n$ 을 구하고 $-1$ 을 하면 $n \times n \le b$ 인 $n$ 을 구할 수 있다. 또한 $n \times n > a$ 인 $n$ 을 다시 구해서 $-1$ 을 하면 $n \times n \le a$ 인 $n$ 을 구할 수 있는데 둘을 빼주면 $a < n \times n \le b$ 인 구간을 얻을 수 있어서 분자를 구할 수 있다.

---

2. 코드

1. 이분 탐색 + 매개 변수 탐색 [Java]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        long cnt = upperBound(b) - upperBound(a);

        if (cnt == 0) {
            System.out.println(0);
        } else {
            long gcd = gcd(cnt, b - a);
            System.out.printf("%d/%d", cnt / gcd, (b - a) / gcd);
        }
    }

    static long upperBound(long key) {
        long left = 0;
        long right = Integer.MAX_VALUE;

        while (left < right) {
            long mid = (left + right) / 2;

            if (mid * mid <= key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

    static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

2. 이분 탐색 + 매개 변수 탐색 [C++]

#include <bits/stdc++.h>
using namespace std;

long long upper_bound_param(long long key) {
    long long left = 0;
    long long right = INT_MAX;

    while (left < right) {
        long long mid = (left + right) / 2;

        if (mid * mid <= key) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    long long cnt = upper_bound_param(b) - upper_bound_param(a);

    if (cnt == 0) {
        cout << 0;
    } else {
        long long g = gcd(cnt, b - a);
        cout << cnt / g << '/' << (b - a) / g;
    }
}

---

3. 풀이 정보

1. 이분 탐색 + 매개 변수 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	112 ms	14563 KB	1076 B

2. 이분 탐색 + 매개 변수 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2020 KB	681 B

---