백준 알고리즘 1052번 물병

백준 1052번

문제 이해하기

처음에는 물병 N개가 이동가능한 K개보다 적은 경우 N을 K개 만큼 추가를 해주어야 된다고 생각했다. (무조건 K개에 맞춰야 옮길 수 있다고 생각했다.) 하지만 요구사항은 K보다 작은 N의 물병이라면 이동이 가능하다고도 해석이 된다.

그렇다면, K보다 작거나 같은 물병수로 만들면 이동이 가능하며 무한히 물병 추가가 가능하다면 결국 짝수개를 맞출 수 있기에 불가능하다는 조건은 없어진다.

첫번째 핵심은 물병의 수가 K보다 작거나 같아야 한다.

물병은 같은 무게의 2개를 하나로 만들 수 있다.

• 1. N=2: [1, 1] -> [2] 한병
• 2. N=3: [1, 1, 1] -> [2, 1] 두병
• 3. N=4: [1, 1, 1, 1] -> [2, 2] -> [4] 한병
• 4. N=5: [1, 1, 1, 1, 1] -> [2, 2, 1] -> [4, 1] 두병
• 5. N=6: [1, 1, 1, 1, 1, 1] -> [2, 2, 2] -> [4, 2] 두병
• 6. N=7: [1, 1, 1, 1, 1, 1, 1] -> [2, 2, 2, 1] -> [4, 2, 1] 세병
• 7. N=8: [1, 1, 1, 1, 1, 1, 1, 1] -> [2, 2, 2, 2] -> [4, 4] -> [8] 한병
• 8. N=9: [1, 1, 1, 1, 1, 1, 1, 1, 1] -> [2, 2, 2, 2, 1] -> [4, 4, 1] -> [8, 1] 두병

규칙을 본다면 물병의 무게는 항상 2의 제곱수로 만들어진다.
이것을 부분집합의 개념으로 바라본다면 N의 값을 2진법으로 나타내었을 때 1을 가진 자리가 각 무게의 물병이 존재함을 알 수 있다.

자세한 내용은 비트마스크를 자세히 공부해보자. 비트마스크 추천링크

두번째 핵심은 N을 2진수로 나타냈을때 "1"의 개수가 물병을 합쳐서 만든 최종 물병의 개수가 된다.

정리하면 물병수 N을 2진수로 나타냈을때 "1"의 총 개수가 K보다 작거나 같으면 물병을 옮길 수 있게 된다.

const getCountBuy = function (N, K) {
  let btlCount = N;
  const canMove = K;
  let bitCount = getBitCount(btlCount); // 2진수로 만들었을때 "1" 의 개수
  let count = 0;

  while (true) {
    if (bitCount > canMove) { // "1"의 개수가 K보다 작거나 같을 때까지
      btlCount++; // 물병수 N에 물병을 계속 추가해준다.
      bitCount = getBitCount(btlCount); // 추가하고 "1" 개수 업데이트
      count++; // 추가 물병수 카운트
    } else break;
  }

  console.log(count);
};

// "1"의 개수 구하는 함수
const getBitCount = function (N) {
  let btlCount = N;
  let arrayBin = btlCount.toString(2).split("");
  let bitCount = arrayBin.reduce((pre, cur) => Number(pre) + Number(cur));

  return bitCount;
};

getCountBuy(1000000, 5);

위 코드와 같이 문제를 풀었을 때 답의 도출은 가능 했지만, 백준 체점에서 시간초과로 실패하게 되었다.
물병수를 K개 만큼 만들때 까지 계속해서 1개의 물병수만 추가하기 때문에 시간의 제한이 크게 적용된다.

const userInput = function () {
  var fs = require("fs");
  var input = fs.readFileSync("/dev/stdin").toString().split(" ");
  var a = parseInt(input[0]);
  var b = parseInt(input[1]);
  getCountBuy(a, b);
};

const getCountBuy = function (N, K) {
  let btlCount = N;
  const canMove = K;

  let originBottle = btlCount; // 최초 N값
  let bin2Str = btlCount.toString(2);
  let bitCount = bin2Str.match(/1/g).length; // "1" 개수 값

  while (bitCount > canMove) { // "1" 개수가 K보다 작거나 같을 때 까지
    // parseInt, substring을 이용하여 "마지막 "1"의 자리"의 "2 자리제곱 값"을 가져왔다.
    btlCount += parseInt(bin2Str.substring(bin2Str.lastIndexOf("1")), 2);
    bin2Str = btlCount.toString(2);
    bitCount = bin2Str.match(/1/g).length;
  }
  console.log(btlCount - originBottle); // +된 물병수 - 최초 물병수 => 카운트
};

userInput();

물병수를 조건까지 +1을 해주는 코드가 아닌 마지막 "1"의 2 자리제곱 값을 바로 가져와서 시간을 줄일 수 있었다.

parseInt radix 공부하기
substring() 복습하기