[python] 백준 - 1052. 물병

🤔문제 해결

• S1 | 이진법

 

1. 물의 양이 1, 2, 4, 8, 16, ... 이렇게 증가하므로 이진수처럼 생겼다.
2. 같은 수를 더하면 다음 수 하나가 나온다. 이진수로 보면
   1. ex) 100 + 100 = 1000
3. 예시로 설명해보자면 N = 11 일 때
   1. 물병: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
      1. 물병합: 2, 2, 2, 2, 2, 1
      2. 물병합: 4, 4, 2, 1
      3. 물병합: 8, 2, 1
4. 물병은 결국 3개가 된다.
5. 11을 이진수로 바꾸면 1011 이다.
6. 결국 1의 개수가 다 합쳤을 때의 물병의 개수가 된다.
7. 그럼 1의 개수를 줄이고 싶으면 이진수 덧셈을 이용한다.
   1. 1011(11) + 0001(1) => 1100(12)
   2. 1100(12) + 0100(4) => 10000(16)

🚀 이진수를 잘 이용해서 문제를 풀어보자!

1씩 증가시켜가면서 확인을해도 통과할 수 있지만 시간차이가 많이 난다.

 

💻소스 코드

# 문제 접근법이 중요하다.
# 뭔가 2진법같이 생겼다.
# 2진법으로 풀어보자

# N을 이진법으로 바꾸면 (ex, 11 => 1011)
# 물병: 1,1,1,1,1,1,1,1,1,1,1
# 합치기: 2,2,2,2,2,1
# 합치기: 4,4,2,1
# 합치기: 8,2,1
# 뭔가 규칙이 보인다.
# 결론: N을 이진법으로 바꾼 수의 1의 개수가
# 물을 최대로 합친 후의 물병의 개수이다.
N, K = map(int, input().split())

purchased_water_bottle_cnt = 0

while bin(N).count('1') > K:
    idx = bin(N)[::-1].index('1')
    purchased_water_bottle_cnt += 2**idx
    N += 2**idx

print(purchased_water_bottle_cnt)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE