백준 19939번 박 터뜨리기 (JAVA)

19939번 박 터뜨리기

문제

난이도

• 실버 5

알고리즘 분류

• 그리디 알고리즘

풀이

각 바구니에는 1개 이상의 공이 존재해야한다.

각 바구니에 들어있는 공의 개수는 모두 달라야 한다.

바구니에 담긴 공의 최대 개수와 최소 개수의 차이를 최소로 하기 위해선 1개 씩 증가하면서 담기

1개씩 증가하면서 담을 수 없는 경우, 공의 개수를 달리하면서 모든 바구니를 채울 수 없다.

1개씩 증가하면서 담을 수 있는 경우,

공을 다 담은 경우 종료

공이 바구니의 개수보다 많이 남은 경우, 각 바구니에 1개 씩 추가

공이 바구니의 개수보다 적게 남은 경우, 공이 많이 담긴 바구니부터 1개씩 추가해야 겹치지 않는다.

코드

public class Main {
    public static void main(String[] args) throws Exception {

        // System.setIn(new FileInputStream("input.txt"));

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(in.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int answer = -1;
        int sum = 0;
        int[] balls = new int[K];
        boolean check = true;

        for (int i = 0; i < K; i++) {
            sum += i + 1;
            balls[i] = i + 1;
            if (sum > N) {
                check = false;
                break;
            }
        }

        while (check) {
            if (N - sum == 0) {
                answer = balls[K - 1] - balls[0];
                break;
            }

            if (N - sum < K) {
                answer = balls[K - 1] - balls[0] + 1;
                break;
            }

            if (N - sum >= K) {
                for (int i = 0; i < K; i++) {
                    balls[i] = balls[i] + 1;
                }
                sum += K;
            }
        }

//        System.out.println(Arrays.toString(balls));

        sb.append(answer);
        out.write(sb.toString());
        out.close();
    }
}