[백준][자바스크립트] 19939번_박 터뜨리기

https://www.acmicpc.net/problem/19939

문제

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1

5 3

예제 출력 1

-1

예제 입력 2

6 3

예제 출력 2

2

 

---

문제 풀이

각 바구니에 최소 1개, 2개, ..., K개씩 공을 담는 것이 가장 균등하게(차이를 최소로) 분배하는 방법이다.
즉, 매 순간 "가장 적게 담긴 바구니에 1개씩 추가"하는 선택이, 전체적으로도 차이를 최소로 만드는 최선의 선택이다.
"현재의 최선 선택이 전체 최선"이라는 그리디 알고리즘의 핵심 조건을 만족한다.

• 핵심 조건
  • N개의 공을 K개의 바구니에 나눠 담는다.
  • 각 바구니에는 최소 1개씩, 그리고 서로 다른 개수의 공이 들어가야 한다.
  • 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공 개수 차이의 최소값을 구한다.
  • 만약 불가능하다면 -1을 출력한다.
• 접근법
  1. 최소한으로 각 바구니에 공을 나눠 담기
     바구니가 K개라면, 첫 번째 바구니에 1개, 두 번째에 2개, ..., K번째에 K개씩 공을 넣는다.
  2. 공이 부족하면 바로 -1 출력
     공을 나눠 담다가 공이 모자라면, 조건을 만족시킬 수 없으므로 바로 -1을 출력하고 종료한다
  3. 남은 공 분배
     위 과정을 마치고 남은 공이 있다면, 남은 공을 바구니에 추가로 분배해야 한다.
     이때, 바구니에 이미 1, 2, ..., K개씩 들어가 있으므로, 남은 공을 K개 바구니에 골고루 나눠주면 된다.
     남은 공을 바구니 수(K)로 나눠떨어지면 모두에게 똑같이 1개씩  더 줄 수 있고, 그렇지 않으면 일부 바구니에만 1개씩 더 주게 된다.

소스코드

[수도 코드]

1. N, K 입력받기
2. 바구니마다 1, 2, ..., K개씩 공을 넣으며 N에서 차감
   for i in 1 to K:
       N -= i
       if N < 0:
           print(-1)
           return
3. 남은 공(N)을 K로 나눠서,
   - N % K == 0이면 print(K-1)
   - 아니면 print(K)

 

[코드 구현]

const fs = require('fs')
const [N, K] = fs.readFileSync('input.txt').toString().split(' ');

function minDifference(n, k) {
  for (let i = 1; i <= k; i++) {
    n -= i;
    if (n < 0) {  // 공이 모자라면
      return -1;
    }
  }

  if (n % k === 0) {
    // 모든 바구니에 똑같이 추가 가능
    // (최대 - 최소) = (K + 추가) - (1 + 추가) = K - 1
    return k - 1;
  }
  // 일부 바구니만 1개 더 받음
  // (최대 - 최소) = (K + 추가 + 1) - (1 + 추가) = K
  return k;
}

console.log(minDifference(N, K));