SWEA 15942. 외계인 침공

행성들을 침략, 동원하여 모든 행성을 정복하려한다. 함선의 갯수보다 인구수가 적은 곳을 침략하여 주민들의 수를 흡수할 수 있다. 동원은 주민들의 수 만큼 함선을 만들 수 있다. 한 행성 당 1번의 동원을 할 수 있을 때, 최소 동원 횟수를 구하는 문제이다. 모든 행성을 정복할 수 없으면 -1을 출력한다.

 

모든 행성들의 인구들을 합해 둔 후, 행성들을 정복하면서 현재 인구수 보다 작게 되면 동원을 종료하고 남은 행성들을 침략하면 된다. 현재 정복 가능한 가장 큰 행성을 침략 후 동원하여 주민들의 수를 최대화해야 최소한의 동원 횟수로 모든 행성을 정복할 수 있다. 이를 위해 배열에 행성들의 인구수를 넣은 후 정렬하였다.

long[] board = new long[n];
boolean[] visited = new boolean[n];
for(int i=0; i<n; i++) {
    long num = Long.parseLong(st.nextToken());
    sum += num;
    board[i] = num;
}
Arrays.sort(board);

 

 

이후, 배열의 맨 앞부터 끝까지 현재 인구수보다 작거나 같은 가장 큰 행성을 정복한 후, 동원한다. 정복하면서 인구수가 남은 행성 수 보다 크거나 같으면 침략만 하면 되므로 횟수를 세지 않고 종료한다. 현재 인구수로 정복할 수 있는 행성이 없다면 정복하지 않은 이전 행성들을 전부 정복하면서 큰 행성을 정복할 수 있을 때 까지 정복한다. 그래도 불가능할 경우, 모든 행성을 정복할 수 없게 되므로 -1을 출력한다. 또한, 최적화를 통해 마지막 행성을 정복했음에도 인구수가 나머지 행성들의 합 보다 작은 경우, 동원 횟수가 필요하므로 인구수가 나머지 행성들의 합보다 크거나 같을 때 까지 남은 가장 큰 행성들을 정복한다.

int count = 0;
           
for(int i=0; i<n; i++) {
    if(k >= sum) break;
    if(i == n-1 && k >= board[i]) {
        for(int j=i; j>=0; j--) {
            if(visited[j]) continue;
            visited[j] = true;
            sum -= board[j];
            k += board[j];
            count++;
            if(k < sum) continue;
            else break;
        }
        if(k < sum) {
            sb.append("-1").append('\n');
            continue out;
        }
        sb.append(count).append('\n');
        continue out;
    } else if(board[i] > k) {
        while(board[i] > k) {
            for(int j=i-1; j>=0; j--) {
                if(visited[j]) continue;
                if(board[j] > k) continue;
                visited[j] = true;
                sum -= board[j];
                k += board[j];
                count++;
                if(board[i] > k) continue;
                else break;
            }
            if(board[i] > k) {
                sb.append("-1").append('\n');
                continue out;
            }
            if(k < sum) {
                if(i == n-1) {
                    for(int j=i; j>=0; j--) {
                        if(visited[j]) continue;
                        visited[j] = true;
                        sum -= board[j];
                        k += board[j];
                        count++;
                        if(k < sum) continue;
                        else break;
                    }
                    if(k < sum) {
                        sb.append("-1").append('\n');
                        continue out;
                    }
                    sb.append(count).append('\n');
                    continue out;
                }
            } else {
                sb.append(count).append('\n');
                continue out;
            }
        }
    } 
}
sb.append(count).append('\n');

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        out: for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            long k = Long.parseLong(st.nextToken());
            long sum = 0L;
            st = new StringTokenizer(br.readLine());
            long[] board = new long[n];
            boolean[] visited = new boolean[n];
            for(int i=0; i<n; i++) {
                long num = Long.parseLong(st.nextToken());
                sum += num;
                board[i] = num;
            }
            Arrays.sort(board);
            int count = 0;
           
            for(int i=0; i<n; i++) {
                if(k >= sum) break;
                if(i == n-1 && k >= board[i]) {
                    for(int j=i; j>=0; j--) {
                        if(visited[j]) continue;
                        visited[j] = true;
                        sum -= board[j];
                        k += board[j];
                        count++;
                        if(k < sum) continue;
                        else break;
                    }
                    if(k < sum) {
                        sb.append("-1").append('\n');
                        continue out;
                    }
                    sb.append(count).append('\n');
                    continue out;
                } else if(board[i] > k) {
                    while(board[i] > k) {
                        for(int j=i-1; j>=0; j--) {
                            if(visited[j]) continue;
                            if(board[j] > k) continue;
                            visited[j] = true;
                            sum -= board[j];
                            k += board[j];
                            count++;
                            if(board[i] > k) continue;
                            else break;
                        }
                        if(board[i] > k) {
                            sb.append("-1").append('\n');
                            continue out;
                        }
                        if(k < sum) {
                            if(i == n-1) {
                                for(int j=i; j>=0; j--) {
                                    if(visited[j]) continue;
                                    visited[j] = true;
                                    sum -= board[j];
                                    k += board[j];
                                    count++;
                                    if(k < sum) continue;
                                    else break;
                                }
                                if(k < sum) {
                                    sb.append("-1").append('\n');
                                    continue out;
                                }
                                sb.append(count).append('\n');
                                continue out;
                            }
                        } else {
                            sb.append(count).append('\n');
                            continue out;
                        }
                    }
                } 
            }
            sb.append(count).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
}