[백준OJ] 22993번 서든어택 3

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

22993번: 서든어택 3

---

 

풀이

준원이에게 가장 좋은 순서가 되기위해선, 공격력이 가장 작은 플레이어부터 차례대로 와가지고, 준원이에게 흡수되는것이 가장 좋은 순서이다.

따라서 준원이를 제외한 다른 플레이어들을 오름차순 정렬을 한 뒤, 앞에서부터 비교해가며

1. 준원이보다 공격력이 작다면 준원이에게 흡수, 마지막 플레이어까지 흡수했다면 True

2. 준원이보다 크거나 같다면 False

를 리턴해주면된다.

 

시간복잡도

정렬은 C++ algorithm의 Sort를 사용했으므로 O(NlogN)이 걸린다.

탐색은 O(N)이 되므로, 총 O(NlogN)이 된다.

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n;
long long jun;
vector<int> v;

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		//준원이 공격력 입력
		if (i == 0) {
			cin >> jun;
		}
		//나머지 공격력 입력
		else {
			int data;
			cin >> data;
			v.push_back(data);
		}
	}
}

bool alive() {
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size();i++) {
		int enemy = v[i];
		if (jun <= enemy) {
			return false;
		}
		else{
			jun += enemy;
		}

	}

	return true;
}

void solve() {
	input();
	if (alive()) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}
}

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

	solve();
	return 0;
}