AOJ - 110 [java] - 문자열, 오름차순

 

핵심 아이디어

최적 전략: 약한 몬스터부터 순서대로 잡으면 레벨이 최대로 오름 → 마왕을 마지막에 도전.

마왕 제외하고 나머지를 오름차순 정렬 → 순서대로 잡을 수 있으면 마왕도 도전.

---

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());

        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            long K = Long.parseLong(st.nextToken()); // 현석이 레벨

            long[] a = new long[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) a[i] = Long.parseLong(st.nextToken());

            sb.append(solve(N, K, a)).append('\n');
        }

        System.out.print(sb);
    }

    static String solve(int N, long K, long[] a) {
        // 마왕 찾기 (최대 레벨)
        long boss = Long.MIN_VALUE;
        for (long monster : a) boss = Math.max(boss, monster);

        // 마왕 제외한 나머지 오름차순 정렬
        long[] others = new long[N - 1];
        int idx = 0;
        for (long monster : a) {
            if (monster != boss) others[idx++] = monster;
        }
        Arrays.sort(others);

        // 약한 것부터 순서대로 처치
        for (long monster : others) {
            if (K <= monster) return "NO"; // 레벨 같거나 낮으면 쓰러짐
            K += monster;                  // 이기면 레벨 흡수
        }

        // 마왕 도전
        return K > boss ? "YES" : "NO";
    }
}

---

흐름 요약

테스트케이스마다
 └─ solve()
      ├─ 마왕(최댓값) 찾기
      ├─ 나머지 오름차순 정렬
      ├─ 순서대로 전투
      │    ├─ 내 레벨 > 몬스터 → 이김, 레벨 흡수
      │    └─ 내 레벨 <= 몬스터 → NO
      └─ 마왕 도전 → 이기면 YES, 지면 NO

주의점: 레벨이 최대 2,000,000,000이고 몬스터가 200,000마리라 다 흡수하면 int 범위 초과 → long 사용.