[15889] 호 안에 수류탄이야!! - Java[자바]

 

 

| 문제 링크

 

 

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

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

 

 

 

 

---

 

 

 

 

 

| 문제

 

1. 첫 줄에는 수류탄을 주고 받을 수 있는 인원 수 N이 주어집니다. (1 ≤ N ≤ 30,000)
2. 다음 줄에 N명의 인원이 서있는 좌표가 N개 주어집니다. (0 ≤ 좌표 ≤ 1,000,000)
3. 그 다음 줄에 N-1명(가장 오른쪽 인원은 던질 사거리가 없음)의 수류탄을 던질 수 있는 사거리가 주어집니다. (0 ≤ 사거리 ≤ 1,000,000)
4. 가장 왼쪽은 수류탄 던지기를 시작할 욱제의 좌표로 0으로 고정이며, 가장 오른쪽에 있는 좌표까지 수류탄을 떨어 뜨리지 않고 옮기면 놀이는 무사히 끝이납니다.
5. 수류탄이 터지지 않고 놀이가 무사히 끝나면 "권병장님, 중대장님이 찾으십니다", 사거리가 부족해 수류탄이 떨어져 터지는 경우 "엄마 나 전역 늦어질 것 같아"를 출력하시오.

 

 

 

 

---

 

 

 

 

| 풀이

 

1. 해당 문제는 그리디 알고리즘 문제로 한쪽 방향으로 쓸면서 탐색하는 모습을 칭해 스위핑 알고리즘이라고도 합니다.
2. n명의 위치를 받는 배열 arr과 n-1명의 사거리를 받는 배열 power에 값을 입력 받습니다.
3. 왼쪽 부터 오른쪽으로 한 칸씩 이동하면서, 현재 좌표(arr의 현재 값) + 사거리(power의 현재 좌표 값)을 더한 값이 max(default = 0)보다 큰 경우 max를 갱신하며, max가 다음 좌표(arr의 다음 값) 보다 작은 경우 땅에 떨어지므로 "엄마 나 전역 늦어질 것 같아"을 출력하며, 마지막 좌표지 탐색이 이어지는 경우 "권병장님, 중대장님이 찾으십니다" 출력.

 

 

 

 

---

 

 

 

 

 

| 코드

 

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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		
		if(n==1) {
			bw.write("권병장님, 중대장님이 찾으십니다");
			br.close();
			bw.close();
		}
		else {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String ans = "권병장님, 중대장님이 찾으십니다";
			//n개의 좌표를 입력 받음
			int[] arr = new int[n];
			for(int i = 0; i<n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			//n-1개의 파워를 입력 받음
			int[] power = new int[n-1];
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i<n-1; i++) {
				power[i] = Integer.parseInt(st.nextToken());
			}
			
			long max = 0;
			//0번쨰 부터 오른쪽으로 하나씩 이동하며 확인, 만약 좌표의 위치+파워의 합보다 다음 좌표가 큰 경우 영창피아노 
			for(int i = 0; i<n-1; i++) {
				max = Math.max(max, arr[i]+power[i]);
				
				if(max<arr[i+1]) {
					ans = "엄마 나 전역 늦어질 것 같아";
					break;
				}
			}
			bw.write(ans);
			br.close();
			bw.close();
		}
	}
}