백준 1094번 : 막대기

mickey·2021년 3월 25일

백준

서론

최근 solved.ac 라는 사이트를 알게되어 백준에서 제공하는 문제의 난이도를 봐 가며 문제를 풀고 있었다.

그러다 문득 1094번을 마주쳤고 순간 멘탈이 흔들렸다.

문제가 이해가 되지 않는다. 그냥 한글이 안 읽힌다.

혹시 글쓴이와 같은 생각으로 구글에 검색했을 독자들을 위하여 어떻게 해결했는지 남겨보겠다.

일단 문제부터 확인해보자.

문제

지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.(X<64)
막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.

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

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

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

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

문제 해석

영어를 번역했는데 뭔가 알아먹기 어렵게 번역된 문체의 느낌이 나서 도무지 뭐라고 하는지 이해가 되지 않았다.

대충 생각해보니 막대기를 계속 자를거고, 그 자른 걸 이어 붙여서 멋진 나만의 막대기를 만든다는 것으로 이해하면 될 것이라고 생각했다.

그렇게 하여 생각해낸 풀이법은 다음과 같다.

어차피 계속 반으로 토막낸 막대를 잇는 것이므로, 잘라낸 막대들은 2의 제곱수로 표현할 수 있다.
ex)
1. 64cm ->32cm x2
2. 32cm -> 16cm x2
3. 16cm -> 8cm x2
4. 8cm -> 4cm x2
5. 4cm -> 2cm x2
6. 2cm -> 1cm x2

그렇게 반으로 잘라낸 막대들로 Xcm 를 만드는 것이다. 그렇다면 X를 2진수로 바꾸어 표현하면 2의 제곱수로 표현된 막대가 몇개가 필요한지 쉽게 알 수 있는게 아닌가?

이해가 되지 않는다면 다음 그림을 보자

10진수로 표기된 숫자를 2진수로 표기하게 되면 각 자리의 숫자가 그림과 같이 표현할 수 있는데, 2의 제곱수로 표현하면 문제에서 원하는 막대의 수가 몇 개인지 쉽게 구할 수 있게 보이지 않는가?

X 라는 숫자를 2진수로 변경하여 1의 갯수만 세어 주면 그게 곧 정답이 되는 것이다.

코드

다음과 같은 생각에서 짜여진 코드는 다음과 같다.

import sys
# 숫자를 입력 받을건데 개행 문자(줄바꿈 문자)를 제거한 숫자만 받겠습니다.
N = int(sys.stdin.readline().rstrip('\n'))

# 입력 받은 숫자를 2진수로 변경합니다.
N = bin(N)

# 입력 받은 숫자를 문자열로 변경하고 count() 라는 함수를 사용하여 
# 2진수로 표현된 값에서 1의 갯수를 세어 출력합니다. 
print(str(N).count('1'))