백준 4159 - 알래스카(자바 - 그리디)

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

4159번: 알래스카

 

* 문제 요약

알래스카 고속도로는 더슨 크릭과 델타 정션을 잇는 길이 1422 마일의 고속도로이다.

전기 자동차를 타고 더슨 크릭에서 출발해 델타 정션에 갔다가 다시 더슨 크릭으로 돌아오려고 한다.

전기 자동차는 한 번 충전하면 200 마일을 이동할 수 있다. 충전소는 더슨 크릭에 있고, 고속도로 중간 중간에도 있다.

충전소의 위치가 주어졌을 때 여행을 성공적으로 할 수 있는지 없는지를 구하는 프로그램을 작성하시오.

 

* 입력

여러개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 고속도로에 있는 충전소의 수 n 이 주어진다. n 은 양의 정수이다.

더슨 크릭에 있는 충전소도 n 에 포함된다.

둘째 줄 부터 n 개 줄에는 충전소의 위치가 주어진다. 위치는 더슨 크릭과 떨어진 거리이며, 0 보다 크거나 같고 1422 보다 작거나 같다.

두 충전소가 같은 장소에 있는 경우는 없다.

입력의 마지막 줄에는 0 이 주어진다.

 

* 출력

각 테스트 케이스마다 전기 자동차를 타고 더슨 크릭에서 델타 정션에 갔다가 다시 더슨 크릭으로 돌아올 수 있으면 POSSBLE 을, 아니면 IMPOSSBLE 을 출력한다.

 

* 예시

 

* 해결 과정

주유소의 위치가 랜덤으로 주어지기에 더슨 크릭에서부터 출발한다는 점. 즉, 0 에서 부터 출발한다는 점을 감안하여 주유소 위치 입력값들을 오름차순 정렬해주었다.

이후 반복을 돌며 현재 탐색으로 찾은 주유소의 위치가 현재 전기 자동차가 이동한 거리보다 가까운 거리에 있을 경우 전기 자동차의 이동 거리를 주유소의 위치 + 200 으로 초기화 해주며 델타 정션까지 갈 수 있는지 확인했다.

 

반복문이 끝나고 난 뒤 이동거리가 1422 보다 크거나 같다면 해당 값에서 1422 를 빼서 델타 정션에 도착한뒤 다시 되돌아가는 거리까지 계산해준 다음, 다시 되돌아간 거리가 주유소의 마지막 위치보다 긴 경우. 즉, 다시 되돌아간 거리 >= 1422 - 마지막 주유소 위치 인 경우 더슨 크릭까지도 충분히 다시 돌아갈 수 있다는 뜻이므로 POSSBLE 을 출력해주고, 그게 되지 않을 경우 IMPOSSBLE 을 출력해줬다.

(어차피 더슨 크릭에서 델타 정션까지 한번 도착한 이상, 델타 정션에서 다시 되돌아간 거리 안에 주유소가 하나라도 존재할 경우 더슨 크릭까지도 충분히 다시 돌아갈 수 있다는 뜻이다.)

그런데 만약 반복문이 끝나고 난 이후 이동거리가 1422 이상이 되지 않는 경우 델타 정션에 조차 도착할 수 없다는 뜻이므로 그 또한 IMPOSSBLE 을 출력해주었다.

 

* 코드

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

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));

        while (true) {
            int count = Integer.parseInt(br.readLine());
            if (count == 0)
                break;
            else {
                int[] powerStation = new int[count];
                for (int i = 0; i < count; i++) {
                    powerStation[i] = Integer.parseInt(br.readLine());
                }

                Arrays.sort(powerStation);
                int distance = 0;
                for (int i = 0; i < powerStation.length; i++) {  
                    if (powerStation[i] <= distance) {
                        distance = powerStation[i] + 200;
                    } else {
                          break;
                    }                   
                }

                // 반대로 돌아서 갈 수 있는지 확인
                if (distance >= 1422) {
                    distance -= 1422;
                    if (distance >= 1422 - powerStation[powerStation.length - 1]) {
                        bw.write("POSSIBLE\n");
                    } else {
                        bw.write("IMPOSSIBLE\n");
                    }

                } else {
                    bw.write("IMPOSSIBLE\n");
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

매 반복마다 현재 탐색중인 주유소의 위치와 현재 이동거리를 계산하여 다음 + 200 위치만큼 이동할 수 있는지 없는지를 판단했으며, 델타 정션에 도착한 이후에도 최종 이동거리와 마지막 주유소의 위치를 감안하여 다시 되돌아 갈 수 있는지 살펴보았다.

뒤에 나올 주유소의 위치와 상관없이 현재 이동거리와 주유소의 위치를 기준으로 로직을 수행하며 더슨 크릭과 델타 정션 사이를 오갈 수 있는지에 대한 전체적인 최적해에 가까운 값을 찾았으므로 그리디 알고리즘 문제에 해당된다.