BOJ - 19939 박 터트리기

문제 링크 : https://www.acmicpc.net/problem/19939

문제 티어: 실버 4

문제 유형: 그리디 알고리즘

문제 풀이 

: N개의 공을 K개의 바구니에 나눠 담아야 하지만 담기는 공의 갯수는 모두 다르게 해야하고 또한 차이는 최소여야 한다는 것이다. 

: 그리디 알고리즘으로 1개씩 공을 다 넣고  Max(공의 갯수) - Min(공의 갯수) 가 최소여야 한다는 것

: 일단 1개씩 공을 다 줌 => 공 남으면 다시 첫 번째로 가서 주고 계속 반복 => 만약 공 다 줬는데 같은 수 있으면 넘어가고 없으면 Max - Min을 해준다.

: 최소 필요한 공 갯수 => 1 + 2 + .... + k = k * (k+1) / 2 

:  만약 공 부족해서 못 나눠주는 경우 console.log(-1);

: 남은 공 수 : remainBalls = N - minBalls

: 만약 남은 공 수가 k로 나누어 떨어진다 => 모든 바구니에 하나씩 줄 수 있다는 점 => k-1개로 차이 유지

ex) n = 9 , k = 3  , minBalls = 1 + 2 + 3 = 6 , n - minBalls = 3 % 3 === 0 => 나누어 떨어짐 = 공 하나씩 줄 수있음 => 차이는 벌어지지 않음

: 만약 남은 공 수가 k로 나누어 떨어지지 않는다면 => 모든 바구니에 하나씩 다 줄 수 없다는 점 => 하나가 늘어나 k개로 크차이 증가 

 

문제 코드

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split(" "); // 공백을 기준으로 나눠서
let [n, k] = input.map(Number);

// 최소 공의 갯수 계산
let minBalls = K * (K+1) / 2;

// 만약 n이 최소 공의 갯수보다 작으면 나눌 수 없으므로 -1 출력
if(n<minBalls){
    console.log(-1);
} else {
     const remainBalls = n - minBalls;
     if(remainBalls % k === 0){
          console.log(k-1);
       } else {
           console.log(k);
           }
 }