백준 15889 - 호 안에 수류탄이야!! (자바-그리디)

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

15889번: 호 안에 수류탄이야!!

 

* 문제 요약

훈련장에 군인들 N 명이 일렬로 서 있다. 군대에 끌려온 사실에 심술이 난 군인들은 수류탄의 안전핀을 뽑아 전우들에게 던지기 시작했다.

군인들은 팔 힘이 모두 다르기 때문에 수류탄을 던질 수 있는 사거리도 모두 다르다. 지금 군인들이 가지고 노는 훈련용 수류탄은 바닥에 떨어지기 전에는 절대 터지지 않는 특수한 수류탄이다.

 

군인들은 특급 전사들이기 때문에 사거리 내에 있는 누구에게나 정확히 수류탄을 던질 수 있고, 마찬가지로 정확히 날아오는 수류탄은 항상 받을 수 있다.

한 위치에 여러 명의 군인들이 서있다면 그 중 아무나 받아 다음 전우에게 던질 수 있다.

누군가의 팔 힘이 모자라 수류탄이 다음 전우에게 전달되지 못하고 바닥에 떨어지는 경우도 있을 수 있다.

이때는 수류탄에서 폭죽이 터지며 불꽃놀이가 시작되고, 동시에 군인들의 영창 생활도 시작된다.

 

이 게임을 중대장님이 모르게 끝마치려면 마지막 전우가 수류탄을 받아 조용히 행사용 폭죽 더미에 섞어놓아야 한다.

전우들은 항상 최선을 다해 최적의 방법으로 게임을 조용히 끝마칠 수 있도록 노력한다.

과연 영창을 건 이 게임의 끝은 어디일까?

 

* 입력

첫째 줄에 전우들의 인원 수 N 이 주어진다. (1 <= N <= 30,000)

둘째 줄에 N 명의 전우들의 좌표가 주어진다. 이는 수직선 위의 음이 아닌 정수로 표현되어 주어지며 시작 좌표는 항상 0 이다. (0 <= 좌표 <= 1,000,000)

N 이 1 보다 크다면, 셋째 줄에 시작점을 포함하고 마지막 전우를 제외한 N - 1 명 전우들의 사거리가 순서대로 주어진다.

N 이 1 이면 셋째 줄이 주어지지 않는다. (0 <= 사거리 <= 1,000,000)

 

* 출력

게임이 조용히 마무리 될 수 있다면 "권병장님, 중대장님이 찾으십니다" 를, 그렇지 않다면 "엄마 나 전역 늦어질 것 같아" 을 출력한다.

 

* 예시

 

* 해결 과정

- 처음 해결했던 방식의 풀이법

N 이 1 인 경우 처음 수류탄을 던지기 시작한 병사가 시작이자 곧 마지막이므로 본인이 던지고 본인이 받아서 폭죽 더미에 수류탄을 섞어 놓는다고 보면 된다.

반대로 N 이 1 보다 클 경우엔 각 병사들이 수류탄을 던질 수 있는 사거리를 감안하여 마지막 병사에게 까지 수류탄을 보낼 수 있는지 계산해야 한다.

수류탄의 사거리 안에 수류탄을 넘겨줄 수 있는 전우들이 여러명 있는 경우 그 사이에 사거리가 가장 긴 병사에게 수류탄을 건네주는 방식으로 문제를 풀었다.

위의 로직을 구현하기 위해 처음엔 이중 반복문을 활용해서 문제를 풀었다.

 

여기서 이중 반복문의 경우 현재 탐색 인덱스의 사거리를 기준으로 넘겨줄 수 있는 좌표에 군인이 있는 경우, 현재까지 찾은 사거리의 최대값과 해당 병사의 사거리를 비교하여 사거리가 더 큰 쪽에 수류탄을 계속 넘겨주는 쪽으로 문제를 풀었다.

 

* 코드

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[] input1 = br.readLine().split(" ");
        String[] input2 = new String[count];
        if (count > 1) {
            input2 = br.readLine().split(" ");
        }

        Soldier[] soldiers = new Soldier[count];
        for (int i = 0; i < count; i++) {
            int coordinate = Integer.parseInt(input1[i]);
            int range = Integer.MAX_VALUE;
            if (i < count - 1) {
                range = Integer.parseInt(input2[i]);
            }

            soldiers[i] = new Soldier(coordinate, range);
        }

        int index = 0;
        while (index < count) {
            Soldier soldier = soldiers[index];
            int max = Integer.MIN_VALUE; // 전달할 수 있는 군인들이 던질 수 있는 사거리 중 최대 사거리

            // 마지막 전우에게 도착한 상태라면 반복문 종료
            if (index == count - 1) {
                break;
            }
            boolean check = false;
            for (int i = index + 1; i < count; i++) {
                // 던질 수 있는 사거리 안에 다음 전우의 좌표가 존재하는 경우
                if (soldier.range >= soldiers[i].coordinate - soldier.coordinate) {

                    check = true;
                    // 현재 최대 사거리보다 더 긴 사거리를 가진 군인을 발견한 경우
                    if (max < soldiers[i].range) {
                        index = i;
                        max = soldiers[i].range;
                    }
                } else if (soldier.range < soldier.coordinate - soldiers[i].coordinate) {
                    break;
                }
            }

            // 현재 군인의 사거리로 누구에게도 수류탄을 전달할 수 없는 경우
            if (!check) {
                bw.write("엄마 나 전역 늦어질 것 같아\n");
                bw.flush();
                bw.close();
                br.close();
                return;
            }
        }

        bw.write("권병장님, 중대장님이 찾으십니다\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

class Soldier {
    int coordinate;
    int range;

    public Soldier(int coordinate, int range) {
        this.coordinate = coordinate;
        this.range = range;
    }
}

 

위와 같은 코드로 통과는 받을 수 있었으나 처리 시간이 1100ms 가 넘길래 나보다 더 빠른 처리 속도로 문제를 풀었던 사람은 어떻게 했는지 확인해보았다.

 

처리 시간을 200ms 남직으로 하여 풀었던 사람은 아래와 같이 문제를 푼 것을 확인할 수 있었다.

핵심은 마지막에 작성되어 있는 반복문인데, 이 반복문에서 계속 현재 좌표와 사거리를 합산한 값과 이전에 탐색했던 좌표 + 사거리 값을 비교하여 더 큰값을 max 변수에 저장해두고, 현재 탐색중인 인덱스의 다음에 있는 좌표가 max 값, 즉 수류탄으로 보낼 수 있는 최대 거리 안 쪽에 있는 경우 다음 탐색으로 넘어가고, 최대 거리 밖에 있는 경우 수류탄을 마지막 까지 보낼 수 없는 것으로 판단했다.

 

위와 같이 로직이 수행될 경우 수류탄의 사거리가 전달 될 수 있는 범위 내부에서 계속 최대값으로 갱신되므로 중간에 현재의 최대값으로도 수류탄이 전달 될 수 없는 좌표가 존재하는 경우가 아니면 반드시 마지막 좌표까지 수류탄이 전달되게 된다.

이중 반복문을 사용하지 않고도 전달 될 수 있는 범위 내부에서 전달 할 수 있는 범위가 더 큰 좌표를 찾아 전달할 수 있음과 동시에, 마지막 까지 전달될 수 없는 경우까지 판단할 수 있다는 것이 인상적이었다.

 

- 처리 시간이 훨씬 빨랐던 통과 코드

import java.io.*;
import java.util.StringTokenizer;

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 [] arr =new int[N];

		StringTokenizer st=new StringTokenizer(br.readLine());
		for (int i=0;i<N;i++){
			arr[i]=Integer.parseInt(st.nextToken());
		}

		boolean FLAG=true;
		if (N==1) {
			System.out.println("권병장님, 중대장님이 찾으십니다");
			return;
		}

		int [] range=new int[N-1];
		st=new StringTokenizer(br.readLine());
		for (int i=0;i<N-1;i++){
			range[i] = Integer.parseInt(st.nextToken());
		}

		long max=0;
		for (int i=0;i<range.length;i++){
			max=Math.max(max,arr[i]+range[i]);

			if (max>=arr[i+1]) continue;
			else {
				System.out.println("엄마 나 전역 늦어질 것 같아");
				return;
			}
		}

		System.out.println("권병장님, 중대장님이 찾으십니다");

	}
}

 

매 반복 단계마다 수류탄이 전달 될 수 있는 최대값이 조건에 따라 갱신되는 식으로 수류탄을 최대한 멀리 보내면서 마지막 좌표까지 수류탄을 보낼 수 있는지 검증하는 방식으로 문제를 풀었다.

현재 상황을 기준으로 수류탄을 전달 할 수 있는 최대 사거리에 대한 갱신(현재 상태에서 최적의 해답을 선택)

그리고 해당 사거리로 다음 좌표의 전우에게 수류탄을 전달 할 수 있는지 확인(선택된 해답이 문제의 조건을 만족하는지 검사)

위의 과정을 반복하며 최종적인 해답, 즉 수류탄을 마지막 좌표에 위치한 전우에게 전달 할 수 있는지 확인하였으므로 그리디 알고리즘 문제에 해당된다.