[백준 1052] 물병 (Python)

👩🏻‍💻문제설명

[백준 1052] 물병 (Python)

✍️Idea Sketch

문제요약

물병이 N개 있는데 1리터씩 들어있다. 물이 든 물병을 K개 이하로 만들어보자.

단, 재분배 규칙은 아래와 같다.
먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 물이 든 물병이 K개 이하가 되면 종료한다.

더이상 물병 두 개를 고를 수 없으면, 상점에서 물병을 살 수 있다. 물은 1리터 들어있다.

목표 : 상점에서 사야하는 물병의 최솟값을 출력하자.

예시

N=3이고, K=1인 경우를 예로 들어보자. 한 병을 또다른 병에 부으면, 2리터 물병 하나와, 1리터 물병 하나가 남는다. 만약 상점에서 1리터 물병 하나를 사면, 2리터 물병 두 개를 만들 수 있다. 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

예제 입력 1
3 1

예제 출력 1
1

예제 입력 2
13 2

예제 출력 2
3

예제 입력 3
1000000 5

예제 출력 3
15808

알고리즘 : 그리디, 비트마스킹

문제에서 주어진 그대로 로직을 작성하지 않고 그리디하게 구현해야 한다. 창의력, 즉 문제를 풀기 위한 아이디어를 떠올리는 능력이 요구된다. 아이디어를 떠올리는 것은 매우 어렵지만, 막상 떠올리고 나면 구현은 쉬운 문제이다.

시간복잡도

O(n)

N은 10^7보다 작거나 같은 자연수이고, K는 1인 최악의 경우를 생각해보자. N개의 물병을 하나로 합쳐야 하므로 10^7보다 크면서 가장 가까운 이진수 x로 만들어야 한다.
실제로 이 이진수 x는 2^24로, 16,777,216이다. (실제 코테에서는 대략 10,000,000 < x < 20,000,000 정도로 고려하고 넘어간다. )
물병을 하나씩 더하는 비효율적인 로직을 짜더라도, 연산 횟수는 16,777,216 - 10,000,000 = 6,777,216 이다. 이는 1억을 넘지 않으므로 시간초과 염려 없이 로직을 짜면 된다.

✍️내 소스코드

Idea

(1) 13의 이진수 1101 → 8리터, 4리터, 1리터 물병 총 3개

(2) 1101를 역순으로 봤을 때 1이 처음 등장하는 인덱스는 0이다.
(3) << 왼쪽 쉬프트 연산자를 사용한다.
(4) 1101 + (1 << 0) = 1101 + 1 = 1110 → 8리터, 4리터, 2리터 물병 총 3개

(5) 1110를 역순으로 봤을 때 1이 처음 등장하는 인덱스는 1이다.
(6) << 왼쪽 쉬프트 연산자를 사용한다.
(7) 1110 + (1 << 1) = 1110 + 10 = 10000 → 16리터 물병 1개

<< 왼쪽 쉬프트 연산자란?

• 쉬프트 연산은 좌항에 있는 피연산자를 우항에 있는 수만큼 비트 자리 이동하는 연산을 수행한다.
• << 는 왼쪽 쉬프트 연산자이고 >> 는 오른쪽 쉬프트 연산자이다.
• << 왼쪽 쉬프트 연산을 하면 좌항에 있는 피연산자의 값이 우항에 있는 수만큼 왼쪽으로 자리 이동하고 빈 자리는 0으로 채운다.

소스코드

  import sys
  si = sys.stdin.readline

  n, k = map(int, si().split())
  m = n

  while bin(m).count('1') > k:
    ridx = bin(m)[::-1].index('1')
    m += (1 << ridx)

  print(m - n)

• 상점에서 1리터 물병을 하나씩 사는 로직 (비효율적)

  import sys
  si = sys.stdin.readline

  n, k = map(int, si().split())
  m = n

  while True:
    cnt = bin(m).count('1')
    if cnt <= k:
      break

    m += 1

  print(m - n)