[13371번] Dolphin

https://www.acmicpc.net/problem/13371

 

 

먼저 이 문제의 n의 조건을 보면

 

For each test case, there is an input n (1 ≤ n ≤ 2 000 000 000)

 

테스트 케이스마다 n의 값이 엄청 크다면 일반적인 탐색으로는 너무 많은 시간이 걸린다.

 

아마 백준에서도 시간초과가 발생할 것이다.

 

따라서 탐색 속도가 빠른 이분 탐색을 사용해야 한다.

 

이 문제를 이분 탐색을 써야하는 이유를 Gemini에게 물어보았다.

 

이분 탐색을 사용해야 하는 이유

1. N이 너무 큽니다: 만약 1라운드부터 k라운드까지 순서대로 n번째가 어디인지 확인하는 반복문(선형 탐색)을 사용하면 k는 약 109까지 증가할 수 있습니다. k 라운드까지의 총 구호 수는 S(k)=3×2k(k+1)​≈1.5k2 입니다. 1.5k2≈1018 이면 k≈1018/1.5​≈109 입니다. 109번의 연산은 1~2초의 시간 제한을 훨씬 초과하여 시간 초과가 발생합니다.
2. 답(k)을 빠르게 찾을 수 있는 '단조 증가' 특성이 있습니다: 우리가 찾아야 하는 것은 " n번째 구호가 몇 라운드( k )에 속하는가?"입니다.
   • k=1 (1라운드)까지의 누적 구호 수: S(1)=3
   • k=2 (2라운드)까지의 누적 구호 수: S(2)=9
   • k=3 (3라운드)까지의 누적 구호 수: S(3)=18
   • k=109 까지의 누적 구호 수: S(109)≈1.5×1018
   k가 커질수록 S(k) 값(누적 구호 수)은 항상 증가합니다. (이를 단조 증가라고 합니다.)이분 탐색은 k의 탐색 범위를 (예: 1부터 2×109까지) 매번 절반씩 줄여나가기 때문에, $O(\log k)$라는 매우 빠른 시간 안에 정답 k를 찾을 수 있습니다. (약 30~40번의 계산만으로 109 범위에서 답을 찾습니다.)
3. 이렇게 값이 정렬된(혹은 순서가 보장된) 상태에서 특정 값(n)을 찾는 가장 빠른 방법이 바로 이분 탐색(Binary Search)입니다. 우리는 S(k)≥n 을 만족하는 가장 작은 k 를 찾고 싶은 것입니다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt(); // 테스트 케이스 개수
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            long n = sc.nextLong();
            long k = 0; // n이 속한 라운드(k)를 저장할 변수

            long low = 1;
            long high = 2000000000;

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

                long shouts = 3L * mid * (mid + 1) / 2L;

                if (shouts < n) {
                    // mid 라운드까지의 구호 수보다 n이 크다.
                    // 정답(k)은 mid보다 큰 쪽에 있다.
                    low = mid + 1;
                } else {
                    // totalShouts >= n
                    // n이 mid 라운드에 포함되거나, 그 이전 라운드일 수 있다.
                    // mid를 정답 후보로 저장하고, 더 작은 k가 있는지 왼쪽(high)을 탐색한다.
                    k = mid;
                    high = mid - 1;
                }
            }

            long prevShouts = 3L * (k - 1) * k / 2L;

            // k 라운드 내에서 n이 몇 번째인지 계산
            long indexInRound = n - prevShouts;

            // k 라운드는 "k dolphin(s)" k개, "k jump(s)" k개, "splash" k개로 구성됨

            if (indexInRound <= k) {
                // "k dolphin(s)" 구간
                if (k == 1) {
                    sb.append("1 dolphin").append("\n");
                } else {
                    sb.append(k + " dolphins").append("\n");
                }
            } else if (indexInRound <= 2 * k) {
                // "k jump(s)" 구간
                if (k == 1) {
                    sb.append("1 jump").append("\n");
                } else {
                    sb.append(k + " jumps").append("\n");
                }
            } else {
                // "splash" 구간 (indexInRound <= 3 * k)
                sb.append("splash").append("\n");
            }
        }

        System.out.println(sb);
    }
}

 

 

여기서 중요한 점은 오버플로우를 조심해야 했다.

 

먼저 기본적으로 n의 범위는 int형 범위로도 충분히 커버가 되었다.

 

그러나

shouts = 3L * mid * (mid + 1) / 2L;

 

해당 연산과정은 int형 범위를 넘어갈 수 있기 때문에 오버플로우 가능성이 발생한다.

 

따라서 안전하게 코드를 설계하기 위해서 int형으로 선언할 수 있는 부분도 long으로 하여 해당 연산에서 발생할 수 있는 문제를 방지했다.

 

물론 해당 연산을 할 때만 부분적으로 처리를 하는 것이 메모리를 고려하였을 때 좀 더 효율적이지만 그럴 경우 long형과 int형이 섞이게 되

 

어 코드를 구현하거나 나중에 읽을 때 더 귀찮아진다는 문제가 더 크다고 생각하여 다음과 같이 설계했다.

 

 

또한 출력 형식에서도 조심해야 하는데 

 

1일 경우에는 단수형으로 2 혹은 이상일 경우는 복수형으로 단어를 출력해야 한다. 

 

그렇기 때문에 다음과 같이 조건문으로 1일 경우와 나머지 경우를 나누어서 출력을 구분하였다.

 

 

또한 필자는 출력이 깔끔하게 한번에 나오는 것을 좋아하고 테스트 케이스가 많을 경우 

 

System.out.println() 은 입력할 때마다 출력이 되어 터미널에서 테스트 할 때 지저분하고 

 

생각보다 입출력 속도가 느린 출력이기 때문에 StringBuilder를 선호하여 다음과 같이 작성하였다.

 

백준을 풀 때 생각보다 System.out.println()의 출력 속도 문제로 인해 시간초과가 나는 경우가 많다.