스터디 23/01/14 22993 : 서든어택 3

22993번: 서든어택 3 (acmicpc.net)

22993번: 서든어택 3

풀이
낮은 공격력부터 높은 공격력 순서대로 정렬 한 후 순서대로 공격하여 모두 처리할 수 있다면 최후의 생존자가 될 최적의 순서이다. A를 정렬한 배열을 B라고 했을 때 Bi <= Bj (i < j) 가 보장되어 있으며 만약 Bi에서 이기지 못한다면 Bj에서도 이기지 못한다는게 자명하므로 순서대로 처리하면 된다. 또한 준원이를 제외한 다른 플레이어끼리 싸워 누군가 한명이 공격력이 증가하면 준원이 입장에서는 손해이므로 오직 준원이와 다른사람끼리만 싸우는 것이 가장 최적의 순서이다.

시간복잡도 : O(nlong) , n <= 1e5

#include<bits/stdc++.h>
#include<time.h>


#define MAX 5000001
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }


ll v[100001];
int main() {
    init();
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v + 1, v + n);
    ll junwon = v[0];
    string ans = "Yes";
    for (int i = 1; i < n; i++) {
        if (junwon <= v[i]) {
            ans = "No";
            break;
        }
        else if (junwon > v[i]) {
            junwon += v[i];
        }
    }
    cout << ans << "\n";
}