[JAVA] 백준 15889 라인 스위핑

 

안녕하세요

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

문제

대한건아 욱제는 수류탄 투척 훈련을 받고 있다. 욱제를 필두로, 훈련장에는 욱제를 포함한 N명의 전우들이 일렬(1열 횡대 ㅎ)로 서있다. 군대에 끌려온 사실에 심술이 난 욱제는 수류탄의 안전핀을 뽑아 전우에게 던졌다. 마찬가지로 심술이 난 전우들도 욱제가 던진 수류탄을 받아 전우들에게 던지기 시작했다.

이 게임을 중대장님이 모르게 끝마치려면 마지막 전우(왼쪽에서부터 N번째 전우)가 수류탄을 받아 조용히 행사용 폭죽 더미에 섞어놓아야 한다. 욱제와 전우들은 항상 최선을 다해 최적의 방법으로 게임을 조용히 끝마칠 수 있도록 노력한다. 과연 영창을 건 이 게임의 끝은 어디일까?

풀이

어떻게 풀까 고민을 하다 왼쪽에서부터 오른쪽 사람으로 스캔해가면서 각 병들이 던질 수 있는 수류탄의 범위를 넓혀가는 방식으로 해결했다.

라인 스위핑

가장 좌측에 병사 한명만 있다면 항상 그대로 종료되기 때문에 br.readLine() 호출하지 않도록 막았다.

st = N > 1 ? new StringTokenizer(br.readLine()) : null;
int line = 0;
for(int i=0; i<N-1; i++){
    range[i] = Integer.parseInt(st.nextToken());
    if(line >= coordinate[i] && line < coordinate[i] + range[i])
        line = coordinate[i] + range[i];
}

현재 서있는 병사까지 수류탄이 닿을 수 있고, 현재 수류탄이 닿을 수 있는 거리가 현재 병사가 서있는 거리 + 현재 병사가 던질 수 있는 거리보다 작다면 수류탄의 범위를 갱신해준다.

출력

최종적으로 수류탄이 갈 수 있는 거리가 마지막 병사까지 닿는 경우 영창에 가지 않을 것이고 마지막 병사까지 닿지 않는다면 영창에 갈것이다!!

if(coordinate[N-1] <= line){
    System.out.println("권병장님, 중대장님이 찾으십니다");
}else{
    System.out.println("엄마 나 전역 늦어질 것 같아");
}

전체 코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] range = new int[N];
        st = N > 1 ? new StringTokenizer(br.readLine()) : null;
        int line = 0;
        for(int i=0; i<N-1; i++){
            range[i] = Integer.parseInt(st.nextToken());
            if(line >= coordinate[i] && line < coordinate[i] + range[i])
                line = coordinate[i] + range[i];
        }

        if(coordinate[N-1] <= line){
            System.out.println("권병장님, 중대장님이 찾으십니다");
        }else{
            System.out.println("엄마 나 전역 늦어질 것 같아");
        }
    }
}

결과