[백준 20916] 안녕 2020 안녕 2021 [Java]

문제

http://boj.ma/20916

20916번: 안녕 2020 안녕 2021

 

 

---

풀이

문제 요약

두 수의 합이 “안녕한 정수”가 되는 쌍의 개수를 구하자.

아이디어

두 수의 합은 최대 9자리 이므로 “안녕한 정수”를 미리 선언하고, “안녕한 정수”에서 임의의 수를 뺀 수를 찾으면 된다. lower/upper bound로 쌍을 세면서 탐색하자.

    static final int[] helloNums = {
            202021, 20202021, 202002021, 202012021,
            202022021, 202032021, 202042021, 202052021,
            202062021, 202072021, 202082021, 202092021
    };
            // Solve
            Arrays.sort(arr);

            long res = 0;
            for (int i = 0; i < N; ++i) {
                for (int helloNum : helloNums) {
                    int val = helloNum - arr[i];
                    int l = lowerBound(arr, val, i + 1, N);
                    int r = upperBound(arr, val, i + 1, N);
                    res += (r - l);
                }
            }

풀이 시간

30분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/20916.java