[백준 문제풀이] 19939 박 터뜨리기

19939 박 터뜨리기

문제

$K$개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다.

우리는 게임을 준비하기 위해서, $N$개의 공을 $K$개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, $N$개의 공을 $K$개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.

게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다.

공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다.

1. $N$개의 공을 $K$개의 바구니에 빠짐없이 나누어 담는다.
2. 각 바구니에는 1개 이상의 공이 들어 있어야 한다.
3. 각 바구니에 담긴 공의 개수는 모두 달라야 한다.
4. 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.

위의 규칙을 모두 만족하며 $N$개의 공을 $K$개의 바구니에 나눠 담을 때, 나눠 담을 수 있는지 여부를 결정하고, 담을 수 있는 경우에는 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 계산해서 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 공의 개수를 나타내는 $N$과 팀의 수를 나타내는 정수 $K$가 주어진다.

출력

 $N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 출력한다.

제한사항

•  $2 \le N \le 100,000$ 
•  $2 \le K \le 1,000$ 

나의 풀이

일단 예시를 써보았다.

6개 공 3개 바구니
1 2 3 => 차이 2 ===> 2
5개 공 3개 바구니
1 2 2 => 만들 수 없음 ===> -1
9개 공 3개 바구니
1 2 6 => 차이 5, 1 3 5 => 차이 4, 2 3 4 => 차이 2 ===> 2
1 2 3 / 1 2 4
8개 공 2개 바구니
1 7 => 차이 6, 2 6 => 차이 4, 3 5 => 차이 2 ===> 2
1 2/2 3/3 4/3 5
12개 공 4개 바구니
1 2 3 6 => 차이 5, 1 2 4 5 => 차이 4 ===> 4

바구니에 담는 공의 개수는 같으면 안되기 때문에 1, 2, 3, ..., n 이런 식으로 먼저 담아야 한다고 생각했다.
이 상황은 k개의 바구니가 있을 때 위 조건을 만족하며 공을 담을 수 있는 최소 공의 개수를 나타낸다.

이에 따른 상황을 몇 가지 나눠보았다.

• case 1 : 최소 공의 개수가 실제 공의 개수보다 클 때

  예를 들어 바구니는 3개인 상황에서 조건을 만족하는 첫번째 경우의 수는 1, 2, 3인데, 이런 경우 공은 최소 6개가 필요하다.

  불가능 하므로 -1을 반환한다.

• case 2 : 최소 공의 개수와 실제 공의 개수가 같을 때

  예를 들어 바구니는 3개일 때 최소 6개가 필요한데, 실제 공이 6개라면 가능한 경우는 1, 2, 3 만 존재한다. 차이는 3-1 = 2가 된다.

  바구니 개수-1 을 반환한다.

• case 3 : 최소 공의 개수가 실제 공의 개수보다 작을 때

  예를 들어 바구니가 3개일 때 최소 6개의 공이 필요한데, 실제 공의 개수는 9개라고 가정한다.

  1, 2, 3 의 경우부터 시작해서 가장 개수가 많은 바구니부터 공을 하나씩 채워야한다. (개수가 적은 바구니부터 채우게 되면 바구니의 공의 개수가 같아진다.)
  1, 2, 4, 1, 3, 4, 2, 3, 4 ... 하나씩 채워간 바구니 안의 공 개수가 실제 공의 개수와 같아지면 그 때 결과를 반환하도록 한다.

// 백준 19939번 박 터뜨리기

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().trim().split(" ");

const n = Number(input[0]); //공의 개수
const k = Number(input[1]); //바구니 개수

function solution(n, k) {
  let ballMin = k * (k + 1) / 2;

  // case 1
  if (ballMin > n) {
    return -1;
  } 
  // case 2
  else if (ballMin === n) { 
    return (k-1);
  }
  //case 3
  else {
    let temp = Array(k).fill().map((_, i) => i+1);

    for (let i = k-1; i >= 0; i--) {
      temp[i]++;
      ballMin++;
      if (ballMin === n) return (temp[k-1]-temp[0]);
      if (i === 0) i = k;
    }
  }
}

console.log(solution(n, k));