[JS][백준]19939_박 터뜨리기

문제 번호

19939번: 박 터뜨리기

 

알고리즘 분류

• 수학
• 그리디 알고리즘

 

문제 풀이

 문제에서 각 바구니당 최소 1개씩의 공은 사용해야하고, 바구니마다 공의 개수가 중복되면 안되며, 모든 공을 사용하라고 했다. 그래서 가장 첫번째 바구니부터 k번째 바구니까지 공의 개수를 1개씩 늘려가면서 집어넣는다고 생각했다. 

 

그래서 1+2+...........k 까지의 합인 k*(k+1)/2 가 n 보다 작다면 문제의 조건에 맞게 바구니에 공을 넣을 수 없다.

 

 공의 개수가 부족하지 않고 공의 개수가 남지않는다면 첫번째와 마지막 k 번째의 차이가 답이된다. 

1, 2, 3, ............ k 개씩 집어넣었으므로 가장 적은개수와 가장 많은개수는 k-1 개만큼 차이가 난다.

 

 만약 공의 개수가 남았다면 반대로 k번째 바구니부터 공을 집어넣어야 공의 개수가 중복되지 않으면서 공을 집어넣을 수 있다. k, k-1 .............3,2,1 순서로 공을 집어넣었기 때문에 공의 개수는 k+1,k....................가 된다. 그래서 가장 적은개수와 가장 많은개수의 차이는 k번쨰와 첫번째의 차이가 된다. (k+1) -1, 즉 k 가 된다.

 

전체코드

const fs = require('fs').readFileSync('박 터뜨리기/input.txt').toString().trim().split(' ').map(x => Number(x));
let N = fs.shift();
const K = fs.shift();

let sum = K*(K+1)/2;
if(sum > N) return console.log(-1);
N -= sum;
if(N%K===0) return console.log(K-1);
else if(N%K!==0)  return console.log(K);

 

특이사항

 다른분의 풀이를 보니까 규칙을 찾아서 푸신분도 계셨다.