[백준] 1052 물병 (Javascript)

잭슨·2024년 4월 24일

백준 알고리즘 자바스크립트

알고리즘 문제 풀이

목록 보기

62/130

문제

BOJ1052_물병

풀이

요구 사항

n개의 물이 있다.
최대한 많은 물을 한 번에 가져가고자 한다.
한 번에 가져갈 수 있는 물병의 개수는 k개다.
물을 재분배 하는 방법은 이렇다.

같은 양의 물이 들어있는 물병 두 개를 고른다.
한쪽의 물병에 다른 한 쪽의 물을 모두 붓는다.
이 방법을 필요한 만큼 계속 한다. (비어있지 않은 병이 k개 이하가 될 때까지)
비어있지 않은 물병을 k개 이하로 만들 수 없을 경우에는 상점에서 물병을 살 수 있고, 상점에서 산 물병에는 1L의 물이 들어있다.

상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

접근 과정

물병의 개수가 K개보다 많다면 물을 재분배 해서 물병의 개수를 K개 이하로 줄여야 하는 문제다.

처음에 제공되는 n개의 물병에는 각각 1L씩의 물이 있다.
물병의 개수를 줄이는 방법은 아래처럼 두 물병을 하나의 물병으로 합치는 것이다.
예를 들어 N=100, K=3 이라고 가정해보자.

물병의 개수	물병 하나당 물의 양(L)	나머지
100	1	0
50	2	0
25	4	0

위와 같이 물병의 개수가 홀수일 경우에는 어떻게 할 수 있을까?

홀수인 경우에는 물병 하나를 잠시 따로 빼놓을 수 있다.

물병의 개수	물병 하나당 물의 양(L)	나머지
24	4	1 x 4
12	8	1 x 4
6	16	1 x 4
3	32	1 x 4

또다시 홀수가 나왔으므로 물병 하나를 잠시 빼놓자.

물병의 개수	물병 하나당 물의 양(L)	나머지
2	32	1 x 4, 1 x 32
1	64	1 x 4, 1 x 32

최종적으로 64L = 1병, 32L = 1병, 4L = 1병 이렇게 총 3병이 만들어진다.

그런데 만약 K=2라면 물병 개수를 더 줄여줘야 한다.

이럴 땐 아까 빼놨던 나머지 물병과 상점에서 새로 구매한 물병을 합쳐주면 된다.

상점에서 물 4병을 사서 이를 4L짜리 1병으로 만들고, 이를 나머지 물병 중 4L짜리 물병과 합쳐주면 8L짜리 물병 하나가 생긴다.

하지만 아직 물병의 개수는 3개이므로 더 줄여줘야 한다.

상점에서 물병 8개를 사서 합치면 16L 한 병이 만들어지고, 다시 물병 16개를 사서 합치면 32L 한 병이 만들어진다.

이를 기존에 있던 32L 한 병과 합치면 64L한 병이 생기고, 최종적으로 64L 물병 2개가 된다. 이를 128L 한 병으로 만들 수도 있겠지만 이미 물병의 개수가 K개 이하이므로 그럴 필요는 없다.

따라서 상점에서 구매한 물병의 수는 4+8+16 = 28개고, 따라서 28이 정답이다.

또한 정답이 없을 경우에 -1을 출력하라는 말이 있는데, 상점에서 물병을 살 수 있는 수가 제한되어 있는 것이 아니니 어떻게 해서든 정답은 구할 수 있으므로 이는 무시해도 된다.

코드 (오답)

내가 말한 조건에 맞게 코드를 작성했는데, 바로 틀렸습니다가 나왔다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const remains = [];
let bottles = N;
let litter = 1;
let answer = 0;

while (bottles >= 1) {
    if (bottles + remains.length <= K) break;
    if (bottles % 2 === 0) {
        bottles /= 2;
        litter *= 2;
    } else {
        remains.push(litter);
        bottles -= 1;
    }
}

let count = 0;
for (let i = 0; i < remains.length - 1; i++) {
    if (remains[i] !== remains[i + 1]) {
        recursion(i);
    }
  	remains[i + 1] += remains[i];
    count++;
    if (bottles + remains.length - count <= K) break;
}

// remains[index] 와 remains[index+1] 을 같은 값으로 만든다.
function recursion(index) {
    answer += remains[index];
    remains[index] *= 2;
    if (remains[index] === remains[index + 1]) return;
    recursion(index);
}

console.log(answer);

접근법이 잘못되었던 건가??
엣지케이스에서 무슨 문제가 있는건가?
반례를 못찾겠다.

코드 (시간 초과)

결국 다른 분의 코드를 참고했다.

문제에서 32L + 32L = 64L처럼 물의 양이 같은 물병끼리 합칠 수 있다고 했다. 이는 $2^5 + 2^5 = 2^6$ 와 같고 2의 제곱수는 이진수로 표현할 수 있다. $0001$ $0000_2+0001$ $0000_2=$ $0010$ $0000_2$ 2의 5승번째 1이 두개가 합쳐지며 2의 6승번째 1이 하나 생겼다.

다시 한번 N=100, k=2 라고 가정해보자.

$N = 100 = 0110$ $0100_2$ 이다. 여기서 1의 개수는 물통의 개수를 의미하기도 한다. $2^6 + 2^5 + 2^2 = 100$ 은 즉, 64L + 32L + 4L = 100L 이기 때문이다.

따라서 N을 이진수로 변환한 다음 1의 개수를 세어주면 되는데, 만약 1의 개수가 K보다 크다면 1의 개수를 작게 만들어줘야 하므로 N에 1씩 더한다.(상점에서 물병을 하나씩 산다.) 그러다보면 이진수의 자리올림이 발생하고, 이는 물병 두개를 하나로 합침을 의미하고 따라서 물병의 개수는 하나 줄어든다.

이렇게 물병의 개수가 K 이하로 내려갈 때까지 반복하며 N에 1씩 더한 카운트를 센다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
let answer = 0;

let n = N;

while (n.toString(2).match(/1/g).length > K) {
    n++; // 상점에서 물병 한 개 추가
    answer++;
}
console.log(answer);

하지만 위 코드는 시간초과가 난다.
알아보니 문자열 <-> 숫자 이렇게 변환하는 과정이 시간이 오래 걸린다고 한다.

따라서 1의 개수를 구하는 방식을 수정해서 통과했다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
let answer = 0;

let n = N;
function countOne(num) {
    let count = 0;
    while (num > 0) {
        if (num % 2 === 1) {
            count++;
        }
        num = num >> 1;
    }
    return count;
}

while (countOne(n) > K) {
    n++; // 상점에서 물병 한 개 추가
    answer++;
}
console.log(answer);

후기

어거지로 비트마스킹 안 쓰고 풀어보려고 했는데, 왜 틀린지 반례도 모르겠고, 비트마스킹을 사용해서 푼 코드는 너무 간결해서 많이 허탈했다.

====================수정====================

비트마스킹 안 쓰고 풀었다!!!!!!!!!

백준 질문 게시판에서 반례 요청했더니 어느 분이 친절하게 반례를 알려주셨다.

원인은 상점을 이용하지 않아도 조건에 만족할 때의 경우를 처리해주지 않아서 그렇다.

수정된 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const remains = [];
let bottles = N;
let litter = 1;
let answer = 0;

while (bottles >= 1) {
    if (bottles % 2 === 0) {
        bottles /= 2;
        litter *= 2;
    } else {
        remains.push(litter);
        bottles -= 1;
    }
}

if (bottles + remains.length <= K) {
    console.log(answer);
    process.exit();
}

for (let i = 0; i < remains.length - 1; i++) {
    if (remains[i] !== remains[i + 1]) {
        recursion(i);
    }
    remains[i + 1] += remains[i];
    bottles++;
    if (remains.length - bottles <= K) break;
}

// remains[index] 와 remains[index+1] 을 같은 값으로 만든다.
function recursion(index) {
    answer += remains[index];
    remains[index] *= 2;
    if (remains[index] === remains[index + 1]) return;
    recursion(index);
}

console.log(answer);