[백준 2024/02/08] 1094번 막대기

https://www.acmicpc.net/problem/1094

1094번: 막대기

 

1. 접근 방법

홀수 인 경우 막대기를 길이가 1이 될 때까지 잘라야 한다.

만약 23을 구하고 싶다면

따라서 필요한 막대기 수에 += 1 을 해주고, 23 -> 22 로 바꾸어서 생각하였다.

 

ex)

22 = 16 + 4 + 2의 막대기를 더해주어야 한다.

 

그랬을 때, 22에 가장 가깝지만, 22 보다 작은 16(2^n) 을 구해준 후, 22- 16을 해준다. 더불어서 필요한 막대기 수에 += 1도 해준다.

 

6이 남게 되고, 6에서 가장 가까운 2^n을 구한다.  가장 가까운 2^n 은 4 이므로, 6-4 = 2를 하고, 필요한 막대기 수에 +=1도 해준다.

 

이제 2가 남게 되고 2에서 가장 가까운 2^n은 2 이므로, 2-2 = 0을 하고, 필요한 막대기 수에 +=1 을 해준다.

 

이런식으로 while 문을 돌려서 문제를 풀어야 겠다고 생각하였다.

 

stick < 2^n 인 n을 구해야 하므로, log2(stick) < n 을 구해주면 된다. 따라서, 하지만 나누어 떨어지지 않을 경우를 대비해서, 

n = int(log2(stick)) 으로 n을 구해주었다.

 

2. 코드

import math

num_stick = 0

stick = int(input())
if stick%2 == 1:
    num_stick += 1
    stick -= 1

while stick:
    n = int(math.log2(stick))
    num_stick += 1
    stick -= 2**n

print(num_stick)