백준 17451번: 평행 우주 (Java)

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

17451번: 평행 우주

 

 

 

 

 

 

 

 

---

 

풀이

1. 이분 탐색

지구에서 올리는 속도 v를 이분 탐색을 통해 최솟값을 찾는 풀이입니다. 최소 속도의 최댓값이 얼마나 될지 살짝 감이 안 잡히나, 9억이 넘는 서로 다른 세 소수 a, b, c (a < b < c)가 차례대로 행성에 도달하는 최소 속도라고 했을 때, 처음 출발 속도는 3*a보다 크거나 같아야 하고, 3*a > (int의 max 범위) 이므로 int 범위를 벗어납니다. 따라서, 일단 long으로 찾아야 한다는 사실을 발견할 수 있습니다. 저는 넉넉하게 n*10^9보다 큰 10^15을 최댓값으로 보아, 이분 탐색에서 r 값을 10^15로 초기화하였습니다.

이후 이분탐색을 합니다. O(nlogn) 시간 복잡도를 가지는 풀이입니다.

 

2. 그리디(정해)

뒤에서부터 앞으로 이동하면서, 각 행성마다 (현재 속력보다 크거나 같으면서 현재 행성의 최소 속도의 배수가 되는 수)만큼으로 속력을 올려줍니다. O(n) 시간 복잡도를 가지는 풀이 방법입니다.

 

되냐/안 되냐가 어떤 변수 값의 크기에 따라 monotone하게 결정되는 상황에서는 이분 탐색을 쓸 수 있습니다. 세그먼트 트리가 그렇듯이, 이분 탐색도 알아두면 그냥 적용해서 뚫어버릴 수 있는 문제가 있는 듯합니다.

 

 

코드

1. 이분 탐색

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));
        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        
        long l = 1, r = (long) 1e15;
        bs: while (l <= r) {
            long mid = (l+r)/2;
            long val = mid;
            if (mid < nums[0]) {
                l = mid + 1;
                continue bs;
            }
            for (int i = 0; i+1 < n; i++) {
                val -= (val % nums[i]);
                if (val < nums[i+1]) {
                    l = mid + 1;
                    continue bs;
                }
            }
            r = mid - 1;
        }
        System.out.println(l);
    }
 
}
 

 

 

2. 그리디

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));
        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        
        long ans = 1;
        for (int i = n-1; i >= 0; i--) {
            ans = (long) Math.ceil((double) ans / nums[i]) * nums[i];
        }
        System.out.println(ans);
    }
 
}
 

 

 

P.S.

Codeforces Round #808 Div.2 C 문제랑 비슷하네요. 차이점이라면, 코드포스 문제가 살짝 더 그리디 풀이가 생각하기 힘듭니다(q가 고정되어 있어서 그런 발상을 제약하는 감이 있습니다.). 신기하게도, 저는 코포 문제를 먼저 접했는데, 저 문제는 그리디로 풀었으면서 이 문제는 이분 탐색으로 풀었네요..ㅎㅎ