[ 백준 / BOJ 17451 ] 평행 우주 ( 자바 / JAVA )

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

17451번: 평행 우주

 

문제

---

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

우리는 현재 지구(=행성 0)에 있다. 여러 요인을 고려한 결과, 행성 1, 행성 2, …, 행성 (n-1)을 순서대로 확인하고 지구(=행성 n)에 돌아오는 것이 비용상 최적임을 알아냈다. 모든 정수 \(1 \leq i < n\)에 대해, 행성 i은 지구가 아니다.

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

다음 지역에 가기 위해서는 원칙적으로는 필요한 속도를 정확히 맞춰야 하지만, 다행히도 평행 우주는 일정한 간격을 두고 있기 때문에 필요한 속도의 양의 정수 배로도 다음 지역으로 이동할 수 있다. 또한, 충분히 빠른 속도로 이동 중이며, 지구의 대체 행성으로 적합한지 아닌지는 도착한 뒤 바로 알 수 있기 때문에 어떤 행성에서는 도달한 뒤 속도를 유지한 채 다음 행성으로 이동할 수도 있다.

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

입력

---

첫째 줄에 n \(1 \leq n \leq 3.105\)이 주어진다.

둘째 줄에 n개의 정수 v1, v2, …, vn이 공백을 사이에 두고 주어진다. 모든 정수 \(1 \leq i \leq n\)에 대해 \(1 \leq vi \leq 109\)을 만족한다.

출력

---

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

풀이

---

Greedy 하게 해결~

맨 마지막 행성부터 진행한다 🤟

속도의 최솟값을 구하면 되기 때문에 마지막 행성에서는 그 행성의 속도와 같은 값이면 충분하기 때문‼️

뒤에서부터 진행하면서,

1️⃣ 현재의 속도 (velocity) 가 i 행성의 속도보다 작으면 👉 velocity = i 행성의 속도

2️⃣ 현재의 속도 (velocity) 가 i 행성의 속도보다 크면 👉 2가지 경우가 나온다

1. 현재의 속도가 i 행성의 속도의 양의 배수이면 👉 상관 ㄴ 진행 ‼️
2. 현재의 속도가 i 행성의 속도의 양의 배수가 아니라면 👉 velocity 값보다 크도록 하면서 i 행성의 속도의 양의 배수로 만들어 준다‼️

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BOJ_17451_평행우주 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

        int n = Integer.parseInt(br.readLine());

        long[] planet = new long[n];
        stringTokenizer = new StringTokenizer(br.readLine());
        for(int i = 0;i < n ; i++){
            planet[i] = Long.parseLong(stringTokenizer.nextToken());
        }

        long velocity = planet[n-1];
        for(int i = n-2; i >= 0; i--){
            if(velocity < planet[i])
                velocity = planet[i];
            else if(planet[i] < velocity && velocity%planet[i] != 0)
                velocity = ((velocity / planet[i]) + 1) * planet[i];
        }
        
        System.out.println(velocity);
    }
}