백준 17451 - 평행 우주 (자바 - 그리디)

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

17451번: 평행 우주

 

* 문제 요약

서기 2xxx 년, 지구가 소행성과 충돌할 위기에 처했다. 똑똑한 과학자 키파는 평행 우주를 누비며 지구를 대신할 행성을 찾는 막중한 임무를 맡게 되었다.

우리는 현재 지구 (= 행성 0) 에 있다. 여러 요인을 고려한 결과, 행성 1, 행성 2, ... 행성 (n-1) 을 순서대로 확인하고 지구 (= 행성 n) 에 돌아오는 것이 비용상 최적임을 알아냈다.

모든 정수 1 <= i < n 에 대해 행성 i 는 지구가 아니다.

지구에는 "초고속 걷기 기계" 라는, 속도를 원하는 만큼 올릴 수 있는 특수한 장치가 있따. 지구를 벗어나면 속도를 떨어뜨릴 수 있을 뿐 높일 수는 없다.

 

다음 지역에 가기 위해서는 원칙적으로는 필요한 속도를 정확히 맞춰야 하지만, 다행히도 평행 우주는 일정한 간격을 두고 있기 때문에 필요한 속도의 양의 정수 배로도 다음 지역으로 이동할 수 있다.

또한, 충분히 빠른 속도로 이동 중이며, 지구의 대체 행성으로 적합한지 아닌지는 도착한 뒤 바로 알 수 있기 때문에 어떤 행성에서는 도달한 뒤 속도를 유지한 채 다음 행성으로 이동할 수도 있다.

 

모든 1 <= i <= n 에 대해, 행성 (i - 1) 에서 행성 i 로 이동하는데 필요한 (최소) 속도 vi 가 주어진다. 지구에서 올려야 하는 속도를 최소화 하시오.

 

* 입력

첫째 줄에 n (1 <= n <= 3*10^5) 이 주어진다.

둘째 줄에 n 개의 정수 v1, v2, ... vn 이 공백을 사이에 두고 주어진다. 모든 정수 1 <= i <= n 에 대해 1 <= vi <= 10^9 를 만족한다.

 

* 출력

수 하나를 첨부한다. 이 수는 지구에서 올려야 하는 속도의 최솟값이다.

 

* 예시

 

* 해결 과정

정확히 필요한 속도에 맞추거나, 필요한 속도의 양의 정수인 경우에만 다음 행성으로 이동할 수 있다.

필요한 속도의 배열을 뒤에서 부터 탐색하며 최종적으로 지구에서 출발할 때 필요한 속도를 찾는 방식으로 문제를 해결했다.

초기 속도를 int 의 최솟값으로 잡아주고 속도 배열의 뒤에서부터 탐색하면서 현재 탐색중인 행성의 탈출 속도가 현재 속도보다 높으면, 현재 속도를 해당 행성의 탈출 속도로 초기화를 해주었다.

만약 현재 속도가 탐색중인 행성의 탈출 속도보다 빠를 경우 다음과 같은 로직을 수행하게끔 했다.

1. 현재 속도와 행성의 탈출 속도를 나눴을 때 나머지가 0 인 경우, 현재 속도가 행성의 탈출 속도의 양의 정수 배에 해당한다는 뜻이므로 아무 로직도 수행하지 않고 다음 탐색으로 넘어간다.

2. 만약 현재 속도가 현재 행성 탈출 속도의 양의 정수 배가 아닌 경우 아래와 같은 공식으로 현재 속도를 현재 행성 탈출 속도의 양의 정수배로 만들어 준 후 다음 탐색으로 넘어간다.

((현재 속도 / 현재 행성 탈출 속도) + 1) * 현재 행성 탈출 속도

* 예시 ) 현재 속도가 400 이고 행성 탈출 속도가 300 인 경우 ((400 / 300) + 1) * 300 = (1+1) * 300 = 600 으로 현재 속도를 행성 탈출 속도 300의 2배인 600 으로 만들어 줄 수 있다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        long[] planet = new long[count];
        for (int i = 0; i < count; i++) {
            planet[i] = Long.parseLong(input[i]);
        }

        long speed = Long.MIN_VALUE;
        for (int i = planet.length - 1; i >= 0; i--) {
            if (planet[i] > speed) {
                speed = planet[i];
            } else if (planet[i] < speed) {
                if (speed % planet[i] == 0)
                    continue;
                else {
                    speed = ((speed / planet[i]) + 1) * planet[i];
                }
            }
        }

        bw.write(speed + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

* 현재 속도와 행성 탈출 속도를 비교하여 조건에 맞춰 현재 속도를 갱신한다.

- 뒤에서 부터 탐색하며 탈출 속도가 현재 속도보다 더 빠른 경우 현재 속도를 탈출 속도 그대로 갱신

(탈출 속도의 1배)

- 현재 속도가 탈출 속도보다 빠를 경우 조건에 따라 현재 속도를 탈출 속도의 양의 정수배가 되게끔 설정

-> (현재 상태에서 최적의 해답을 선택한다.)

 

* 위에서 최적의 해답을 선택할 때 현재 속도가 탈출 속도의 양의 정수배여야 한다는 조건이 만족되게끔 현재 속도를 갱신한다.

-> (선택된 해가 문제의 조건을 만족하는지 검사한다.)

 

위의 2가지 근거를 통해 이 문제가 그리디 알고리즘 문제라는 것을 알 수 있다.