미소를뿌리는감자의 코딩
[백준 2024/02/08] 1094번 막대기 본문
728x90
https://www.acmicpc.net/problem/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)
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/02/11] 1260번 DFS와 BFS (0) | 2024.02.11 |
---|---|
[백준 2024/02/10] 5397번 키로거 (1) | 2024.02.11 |
[백준 2024/02/08] 11279번 최대 힙 - python ver. (0) | 2024.02.08 |
[백준 2024/02/08] 1927번 최소 힙 - python ver. (0) | 2024.02.08 |
[백준 2024/02/07] 17219번 비밀번호 찾기 (0) | 2024.02.07 |