[백준/파이썬] 1052 물병 - 구현

문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다. 물은 다음과 같이 재분배 한다.

• 먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

입력

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

출력

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

---

구현 아이디어

• 문제 설명이 다소 장황하기도 하고 바로 머리에 그려지지 않아서 예제를 관찰해서 규칙을 발견하고자 함
• 같은 양의 물이 들어있는 물병끼리만 합칠 수 있음 → 물병의 무게가 항상 2의 거듭제곱수
• 수식으로 정리했을 때 이진수로 변환하는 로직과 동일함
• 결국 물병을 몇 개 추가해야하는지를 구하려면, 2의 거듭제곱으로 최대한 쪼개야 함
• 물병을 추가하기 전 마지막 단계를 이진수로 표현 가능
  
  • 예를 들어 n=13인 경우 1011로 표현 가능
• 변환된 이진수에서 1의 개수가 곧 현재 물병의 개수
• 이진수에서 1의 개수가 k개와 같아질 때까지 반복문을 실행해서 두 물병을 합친다
  • 이때 n += 1, answer += 1

코드 1 성공

# n = 13, k = 2
n, k = map(int, input().split())

answer = 0

# bin(n) = 1011
# 1의 개수 = (현재 단계에서 물병의 개수)
# 1의 개수 < k : answer = 0
# 1의 개수 > k : 반복문을 실행하면서 물병을 하나씩 추가
#   			 k보다 작거나 같아지면 반복문 탈출
while bin(n).answer('1') > k:
    n = n + 1
    answer = answer + 1

print(answer)

코드 2 실패

n, k = map(int, input().split())

term = 0 # 항의 개수
answer = 0

# 이진수로 변환하는 거랑 로직이 비슷할 것 같은데
save = []
while True:
    a = n // 2
    b = n % 2
    save.append(b)
    if a != 0:
        n = a
    else:
        break

term = save.count(1) # 항의 개수

if term <= k:
    answer = 0
else: # 물병이 총 k개가 되도록 물병 여러 개를 합쳐야 함
    while True:
        first_index = save.index(1)
        save[first_index] = 0
        second_index = save.index(1)
        save[second_index] = 0
        answer += 2 ** second_index - 2 ** first_index
        next_index = second_index + 1
        # save의 next_index 값을 1로 바꿔야 함
        if next_index < len(save):
            while True:
                if save[next_index] == 0:
                    save[next_index] = 1
                    break
                else:
                    next_index += 1
                    if next_index == len(save):
                        save.append(1)
                        break
        else:
            save.append(1)
        term -= 1
        if term == k:
            break
print(answer)

# 풀이가 잘 떠오르지 않는다며 예제를 통해 관찰하기!
# 10진수 -> 2진수 변환 코드 https://codeuniv.tistory.com/58
# 파이썬 index 함수
# 테스트 케이스는 다 통과하는데 자꾸 틀렸다고... 반례가 무엇이 있을까...?

• 풀이 방법을 생각하고, 바로 직관적으로 작성한 코드
• 이진수로 변환해주는 함수 bin을 몰라서 직접 이진수로 변환하는 함수 구현
• 이진수를 리스트로 저장, 리스트의 값(0 또는 1)이 곧 물병의 개수
• 테스트케이스는 다 통과하는데 틀림. 반례를 못 찾겠음

주요 개념

• bin() : 전달 받은 integer 혹은 long integer 자료형의 값을 이진수(binary) 문자열로 반환해주는 함수

  >>> bin(10)
  '0b1010'