[C++] BOJ 15889번 : 호 안에 수류탄이야!!

시간제한	메모리제한	알고리즘 분류
2 초	512 MB	그리디, 정렬, 스위핑

 

문제

“호 안에 수류탄!!”
대한건아 욱제는 수류탄 투척 훈련을 받고 있다. 욱제를 필두로, 훈련장에는 욱제를 포함한 N명의 전우들이 일렬(1열 횡대 ㅎ)로 서있다. 군대에 끌려온 사실에 심술이 난 욱제는 수류탄의 안전핀을 뽑아 전우에게 던졌다. 마찬가지로 심술이 난 전우들도 욱제가 던진 수류탄을 받아 전우들에게 던지기 시작했다. 
이제 수류탄은 뜨거운 감자처럼 욱제와 전우들 사이를 옮겨 다닌다. 전우들은 팔 힘이 모두 다르기 때문에 수류탄을 던질 수 있는 사거리도 모두 다르다. 욱제와 전우들이 가지고 노는 훈련용 수류탄은 바닥에 떨어지기 전에는 절대 터지지 않는 특수한 수류탄이다.
욱제와 전우들은 특급 전사이기 때문에 사거리 내에 있는 누구에게나 정확히 수류탄을 던질 수 있고, 마찬가지로 정확히 날아오는 수류탄은 항상 받을 수 있다. 한 위치에 여러명의 전우가 서있다면 그 중 아무나 받아 다음 전우에게 던질 수 있다.
누군가의 팔 힘이 모자라 수류탄이 다음 전우에게 전달되지 못하고 바닥에 떨어지는 경우도 있을 수 있다. 이때는  수류탄에서 폭죽이 터지며 불꽃놀이가 시작되고, 동시에 욱제와 전우들의 영창 생활도 시작된다.
???: “중대장은 오늘 너희에게 큰 실망을 했다”
이 게임을 중대장님이 모르게 끝마치려면 마지막 전우(왼쪽에서부터 N번째 전우)가 수류탄을 받아 조용히 행사용 폭죽 더미에 섞어놓아야 한다. 욱제와 전우들은 항상 최선을 다해 최적의 방법으로 게임을 조용히 끝마칠 수 있도록 노력한다. 과연 영창을 건 이 게임의 끝은 어디일까?

입력

첫째 줄에 욱제를 포함한 전우들의 인원 수 N이 주어진다. (1 ≤ N ≤ 30,000)
둘째 줄에 욱제를 포함한 N명 전우들의 좌표가 주어진다. 이는 수직선 위의 음이 아닌 정수로 표현되어 주어지며 욱제의 좌표는 항상 0이다. (0 ≤ 좌표 ≤ 1,000,000)
N이 1보다 크다면, 셋째 줄에 욱제를 포함하고 마지막 전우를 제외한 N-1명 전우들의 사거리가 욱제부터 순서대로 주어진다. N이 1이면 셋째 줄이 주어지지 않는다. (0 ≤ 사거리 ≤ 1,000,000)

출력

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

제한

• 1 ≤ N ≤ 30,000
• 0 ≤ 좌표 ≤ 1,000,000
• 0 ≤ 사거리 ≤ 1,000,000

---

문제 해결 조건

게임이 조용히 마무리될 수 있는 조건? 문제에서 주어진 출력은 게임이 몇 번 반복되는지가 아니며, 마무리 여부만을 확인하면 된다.
전제 조건으로 욱제와 전우들이 수직선상에 위치하고 있으므로 한 전우의 좌표와 사거리 데이터를 바탕으로 다른 전우와 비교하였을 때 (현재 좌표 + 사거리 > 다른 전우 좌표) 케이스가 없는 경우 영창이다. 

따라서, 최댓값을 구하는 프로그램과 유사하지만 약간의 변형을 취한다.

* 1.(사거리) 랜덤하게 수류탄을 주고 받아야 하므로, 사거리가 0인 친구가 있으면 그 친구가 마지막 전우에게 수류탄을 전달할 수 없으므로, 사거리 원소 중에 0이 있다면 "엄마 나 전역 늦어질 것 같아" 출력

* 2.(좌표) 사거리 내의 전우에게만 수류탄을 던진다. 현재 좌표 + 사거리 < 다른 전우 좌표 인 경우 "엄마 나 전역 늦어질 것 같아"

 

해결하기 위한 진행 과정 1차

1. 전우들의 숫자 n을 입력받는다.

2. 입력받은 좌표 x값 변수를 저장하는 배열 혹은 벡터를 만든다.

3. 각 전우의 사거리를 순서대로 입력받아 그 전우의 좌표값과 더하고, "(현재 좌표 + 사거리) < 최대 사거리" 조건을 이용해 다른 전우에게 수류탄을 전달할 수 있는지 확인한다.

 

1차 시도에서 헷갈렸던 점

이 문제에서 가장 헷갈렸던 점은 문제를 해석하기 어려웠던 점이다. 사거리가 0인 경우 다른 전우에게 수류탄을 전달할 수 있는가? 그리고 단순히 다음 사람의 좌표와 max값만을 비교하는 for statement로 문제를 해결할 수 있는지 확신할 수 없었다. 전우 각각의 max값(pos[i-1] + dist)을 구했으면, 다음 사람인 pos[i]와의 비교뿐 아니라, 세번째 다음 전우의 좌표도 비교해야하지 않나..? 그래서 for문을 한번 더 반복해야만 할 것 같은 기분이 들었으나 그렇게 진행하지 않아도 성공으로 통과했다. 이건 반복문의 구조에 대해 더 깊은 이해를 해야할 것 같다. 

/* BOJ 15889 : 호안에 수류탄! */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
	int n;
	cin >> n;
	if (n > 1) {
		//전우들의 좌표를 벡터에 저장한다
		vector<int> pos;
		for (int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			pos.push_back(x);
		}
		int dist, max = 0;
		for (int i = 1; i < n; ++i)
		{
			cin >> dist;
			if (max < pos[i - 1] + dist) max = pos[i - 1] + dist;
			if (max < pos[i])
			{
				cout << "엄마 나 전역 늦어질 것 같아";
				return;
			}
		}
	}
	cout << "권병장님, 중대장님이 찾으십니다";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
}