[백준 17451] 평행 우주 (JAVA)

백준(BOJ) 17451 평행 우주

 

난이도
221225 기준 실버 3

사용 알고리즘
그리디

문제 링크
https://www.acmicpc.net/problem/17451

17451번: 평행 우주

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

 우리는 현재 지구(=행성 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을 만족한다.

 

출력

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

 

 

 

2. 어떤 알고리즘을 사용할 것인가

 

어떤 알고리즘을 쓸지는 모르겠는데 아무튼 어떻게 풀면 될 거 같은데? == 그리디 문제입니다.

 

 

3. 풀이 구상

 

지구에서 올려야 하는 속도의 최솟값을 0으로 시작하고

각 행성의 필요속도를 arr에 담은뒤 뒤에서부터 확인합니다.

확인 한 결과 현재 최솟값보다 해당 행성의 필요속도가 높다면 최솟값을 그 행성의 필요속도로 맞춰줍니다.

반대로 최솟값이 더 높다면 최솟값을 그 행성의 필요속도의 배수 중 최솟값 이상인 가장 작은 값으로 맞춰줍니다.

 

 

4. 코드 작성

 

1. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

// 백준 17451 평행 우주
public class Main {

	static int n;
	static int[] arr;
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
   
    	n = Integer.parseInt(br.readLine());
    	arr = new int[n];
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	for(int i = 0; i < n; i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	long speedMin = 0;
    	
    	// 뒤에서부터 앞으로 가면서
    	// 현재 speedMin보다 행성의 필요속도가 높다면 speedMin을 그 행성의 필요속도로 맞춰줌
    	// 반대로 speedMin이 더 높다면 행성의 필요속도의 배수중 speedMin을 넘기는 가장 최소의 값으로 맞춰줌
    	for(int i = n-1; i >=0; i--) {
    		if(speedMin <= arr[i]) {
    			speedMin = arr[i];
    		} else if(speedMin > arr[i]) {
    			long div = (speedMin / arr[i]);
    			if(speedMin%arr[i]!=0) {
    				div++;
    			}
    			speedMin = arr[i] * div;
    		}
    	}
    	
    	bw.write(speedMin+"");
    	bw.flush();
        bw.close();
        br.close();
    }
    	
 

}

 

 

2. 오답노트

 

 행성의 필요속도의 배수가 현재 speedMin과 같은 경우를 생각했어야 했는데 초과로만 해버려서 한 번 틀렸습니다. 다른 부분에서는 크게 문제 될 부분은 없어보입니다.

 

---

 

풀이 후기

 사실 이 문제를 처음 읽었을 때 무슨 소리인지 이해가 안가서 여러번 읽었습니다. 실제 기업 코딩테스트에서도 문제가 읽기 쉽게만 나오지는 않을 것이기에 가끔 이런 문제가 나와도 문제 이상하다고 안 풀지 말고 나름 해석해서 풀어나가는 경험을 해보는것도 좋아보입니다.