[백준] 19939번 박 터트리기 (Java)

subbni·2024년 4월 26일

그리디 등차수열 백준 코딩테스트

백준

목록 보기

15/24

19939번 문제

문제

풀이

접근 포인트

각 바구니에는 1개 이상의 공이 들어가 있어야 하며, 각 바구니에 담긴 공의 개수는 모두 달라야 한다.
→ 등차수열의 합 이용

이 문제의 키 포인트는 등차수열의 합을 생각해내는 것인 것 같다.
N개의 공을 K개의 바구니에 빠짐없이, 그 수가 모두 다르게 넣으려면
( 1, 2, 3, ..., k ) 로 넣을 수 있어야 한다.
이를 검증하는 방법은 N이 1+2+3+...+k (= a가 1이고 공차가 1인 등차수열의 k항까지의 합)과 같거나 큰 지를 확인하는 것이다.

크지 않다면, 일단 위의 조건을 만족하지 못 한다는 뜻이 되므로, -1을 출력하여야 한다.

만일 N = 1+2+3+...+k 라면, 위의 모든 조건을 만족하므로 답은 k-1이 된다.
만일 N > 1+2+3+...+k 라면, 위처럼 공을 넣고도 남는 숫자가 있다는 뜻이므로, 이 남는 숫자들을 처리해주어야 한다.

남은 숫자를 각 바구니에 담긴 공의 개수가 모두 다르게, max와 min 공의 개수차가 최소가 되도록 처리
→ 가장 큰 수부터 아래로 내려가면서 1씩 증가시킨다.

가장 큰 수부터 아래로 내려가야 숫자가 중복될 일이 없다.
또한 만일 남는 수가 k로 정확히 나누어진다면 각 바구니에 전부 숫자가 1씩 더해져, 공의 개수차엔 변화가 없다.
남는 수가 k로 나누어 떨어지지 않을 때, 가장 작은 수와 가장 큰 수의 차이가 1이 더 생겨난다.

제출 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int sigma = getSigma(k);
        if(n<sigma) {
            bw.write(-1+"");
        } else {
            int dif = k-1;
            if((n-sigma)%k != 0) {
                dif++;
            }
            bw.write(dif+"");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static int getSigma(int n) {
        int result = 0;
        for(int i=1; i<=n; i++) {
            result += i;
        }
        return result;
    }

}