[자바] 백준 24508 - 나도리팡 (boj java)

문제 : boj24508

 

  그리디로 생각해보자. 결국 최소 횟수로 이동하면서 K개씩을 만들려면 더 빠르게 없어질 수치가 큰 값에다, 더 느리게 없어질 수치가 작은 값을 밀어넣어야 한다. 따라서 입력으로 들어온 N개의 입력값 Ai 들을 정렬해보자. 그리고 작은 값을 큰 값에 직접 밀어넣으면서 K개를 만들면 없애는 식으로 시뮬레이션을 진행하면 풀 수 있다. 약간의 그리디가 들어간 시뮬레이션 문제로 구현력(?)이 좋다면 어렵지 않게 풀 수 있다. 이하의 코드를 참고해보자.

 

  다만 주의해야 할 예시 2가지를 들어보겠다.

[1]
3 2 10000
0 0 0

[2]
5 2 10000
1 0 0

[1] 처럼 모두 0인 경우엔 이미 조건을 만족하므로 별다른 처리없이 YES를 출력해줘야 한다.

[2] 처럼 하나만 0이 아닌 경우엔, 입력 조건에서 Ai < K 라고 했으므로 절대 만족할 수 없으므로 NO를 출력해줘야 한다.

 

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        int notZeroCnt = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (arr[i] != 0)
                notZeroCnt++;
        }
        if (notZeroCnt == 0) {
            System.out.println("YES");
            return;
        } else if (notZeroCnt == 1) {
            System.out.println("NO");
            return;
        }
        Arrays.sort(arr);
        int low = n-notZeroCnt;
        int high = n-1;
        while (t>0 && low<high) {
            int remain = k-arr[high];
            if (arr[low] < remain) {
                arr[high]+=arr[low];
                t-=arr[low];
                low++;
            } else {
                arr[high]+=remain;
                arr[low]-=remain;
                t-=remain;
                high--;
                if (arr[low]==0)
                    low++;
            }
        }
        System.out.println(low>high&&t>=0?"YES":"NO");
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}