백준15889 호 안에 수류탄이야!!

작성일 | In

문제 링크

  • http://icpc.me/15889

문제 출처

  • 제2회 천하제일 코딩대회 예선 E번

사용 알고리즘

  • 그리디

시간복잡도

  • O(n2)

풀이

전우들을 좌표 순으로 정렬을 한 뒤, 만약 같은 자리에 있다면 사거리가 긴 사람만 남겨놓습니다.
이제, 욱제부터 시작해서 모든 전우들을 순회하면서 던져 줄 수 있는 전우에 체크를 해나갑니다.
만약 체크가 안된 전우가 있다면 욱제의 전역이 늦어질 것이고, 반대의 경우에는 중대장이 욱제를 찾을 것입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

int n;

struct asdf{
	int pos, ran;
};

asdf arr[30001];
asdf ori[30001];
int chk[30001];

bool cmp(asdf a, asdf b){
	return a.pos < b.pos;
}

int main(){
	scanf("%d", &n);
	for(int i=0; i<n; i++) scanf("%d", &arr[i].pos);
	if(n == 1){
		printf("권병장님, 중대장님이 찾으십니다");
		return 0;
	}
	for(int i=0; i<n-1; i++) scanf("%d", &arr[i].ran);
	arr[n-1].ran = 0;
	sort(arr, arr+n, cmp);


	int idx = 1;
	ori[0] = arr[0];
	for(int i=0; i<n; i++){
		if(ori[idx-1].pos != arr[i].pos) ori[idx++] = arr[i];
		else ori[idx-1].ran = max(ori[idx-1].ran, arr[i].ran);
	}

	chk[0] = 1;
	for(int i=0; i<idx; i++){
		for(int j=i+1; j<idx; j++){
			if(ori[j].pos-ori[i].pos <= ori[i].ran){
				chk[j] = 1;
			}else break;
		}
	}

	for(int i=0; i<idx; i++) if(!chk[i]){ printf("엄마 나 전역 늦어질 것 같아"); return 0;}
	printf("권병장님, 중대장님이 찾으십니다");
}