문제

지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.

막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.

1. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.

   1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
   2. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.

2. 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.

X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.

출력

문제의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 출력한다.

헤맸다. 조건대로 코드를 짜려니 십중팔구 시간초과 블랙홀에 빠질 듯. 그러다 비트마스크 기법을 알게 됐다. 참조 처음엔 이해하기 어려웠는데, 차근차근 읽다보니 개념이 좀 잡힌다.

문제를 잘 읽어보자. 64cm 막대를 절반씩 쪼개가며 써야 한다. 이를테면,

l = [1, 2, 4, 8, 16, 32, 64]

인 셈이다. 이를 다시 표현하면,

l = [2⁰, 2¹, 2², 2³, 2⁴, 2⁵, 2⁶]

와 같다. 순서를 거꾸로 하면 이진법이다.

7개의 막대 중 몇 개의 막대를 사용하는가? 이 질문은 곧 해당 숫자를 이진법으로 바꾸었을 때 ‘1’이 몇 개인지 묻는 문제다. 위 그림을 보자. 13cm 막대를 만들려면 2³(8), 2²(4), 2⁰(1) 이렇게 3개의 막대가 필요하다.

이제 코드는 간단해졌다.

n = int(input())
b = format(n, 'b') # 십진수를 이진수로 변환
print(b.count('1'))

비트마스크 기법을 활용한 대표 문제로 '외판원 순회 문제'(Traveling Salesman Problem, TSP)(참조1, 참조2)란 게 있다는 걸 알게 됐다. 나중에 시간 여유를 두고 차분히 공부해볼 예정.

[문제 보기]