추석 연휴 전에 쉬운 문제 풀이
대망의 두번째 문제!

BOJ 1094 - 막대기 링크
(2022.09.08 기준 S5)
(치팅 놉! 이라기엔 너무 쉬운 문제)

문제

64cm의 막대기로 절반으로 자르고 하나는 버리거나 붙이고 하나는 다시 자르면서 X cm의 막대기를 만든다고 하면, X cm의 막대기를 만들 때 붙인 막대기의 개수

알고리즘

비트마스킹. 자세한건 풀이에서 후술.

풀이

만약에 35 cm가 필요하다고 가정을 해보자.

• 64 cm의 절반은 32 cm. 32 cm보다 35 cm가 크므로 32 cm 막대기 하나 저장. 남은건 3 cm.
• 32 cm의 절반은 16 cm. 16 cm보다 3 cm가 작으므로 16 cm 막대기 하나 버림.
• 16 cm의 절반은 8 cm. 8 cm보다 3 cm가 작으므로 8 cm 막대기 하나 버림.
• 8 cm의 절반은 4 cm. 4 cm보다 3 cm가 작으므로 4 cm 막대기 하나 버림.
• 4 cm의 절반은 2 cm. 2 cm보다 3 cm가 크므로 2 cm 막대기 하나 저장. 남은건 1 cm.
• 2 cm의 절반은 1 cm. 남은 거와 동일하므로 1 cm 막대기 하나 저장. 남은건 0 cm.

32 cm, 2 cm, 1 cm 막대기 3개가 필요하다.
여기서 감이 오지 않는가?
35의 이진수는 100011이다.

그렇다. 이 문제의 정답은 이진수로 나타냈을 때의 1의 개수이다.
이 막대기는 2의 6제곱인 64에서 시작하여 절반으로 잘라나가고 같은 길이의 막대기는 하나만 쓰이기 때문에, 이진수 표현법과 같다고 볼 수 있다.

코드

# 이진수로 나타냈을 때의 1의 개수를 출력
print(bin(int(input())).count('1'))

여담

역대급으로 짧은 코드. 이것이 바로 숏코딩?