[백준/Java] 15889번 호안에 수류탄이야!!

문제

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

---

문제 이해

• 전우 N명이 수직선 상에 일렬로 서 있고, 욱제는 항상 pos[0] = 0에 위치함
• 각 전우는 자신의 사거리 범위 내 전우에게 수류탄을 던질 수 있음
• 수류탄이 마지막 전우(인덱스 N-1)까지 전달되면 성공, 중간에 멈추면 실패

---

문제 풀이 방법

그리디 + 스위핑 알고리즘

• 왼쪽부터 오른쪽으로 전우들을 순회하면서
• 현재까지 도달 가능한 최대 거리(maxReach)를 갱신
• 다음 전우가 maxReach보다 멀리 있으면 → 수류탄 떨어짐 → 실패

---

코드

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

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[] pos = new int[N];           // 위치 배열
        int[] range = new int[N - 1];     // 사거리 배열

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

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

        int maxReach = 0; // 현재까지 도달 가능한 가장 먼 위치
        int i = 0;        // 지금 탐색할 사람의 인덱스

        for (; i < N - 1 && pos[i] <= maxReach; i++) {
            int reach = pos[i] + range[i];     // 이 전우가 던질 수 있는 거리
            maxReach = Math.max(maxReach, reach); // 최대 도달 위치 갱신

            // 다음 전우가 pos[]에 정렬되어 있으므로 i만 증가
        }

        // 마지막 전우의 위치가 maxReach 이하라면 도달 가능
        if (pos[N - 1] <= maxReach) {
            System.out.println("권병장님, 중대장님이 찾으십니다");
        } else {
            System.out.println("엄마 나 전역 늦어질 것 같아");
        }
    }
}

---

코드 설명

int N = Integer.parseInt(br.readLine());
int[] pos = new int[N];
int[] range = new int[N - 1]; // 마지막 전우는 던지지 않음

• pos[i]: i번째 전우의 위치
• range[i]: i번째 전우가 수류탄을 던질 수 있는 거리
• N-1명까지만 사거리를 입력받는 이유는 마지막 전우는 ****던지지 않기 때문

for (int i = 0; i < N - 1 && pos[i] <= maxReach; i++) {

• i번째 전우의 위치가 maxReach보다 작거나 같아야만 도달 가능
• 만약 pos[i] > maxReach가 되먄, 수류탄 전달 불가 → break

int reach = pos[i] + range[i];

• i번째 전우가 수류탄을 던질 수 있는 최대 거리 계산

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

• 마지막 전우의 위치pos[N-1]가 현재까지의 maxReach보다 작거나 같으면 도달 가능
• 그 외의 경우는 전달 도중 수류탄이 바닥에 떨어진 것……

시간복잡도 : O(N)