[백준][1094] 막대기

• Problem Link : https://www.acmicpc.net/problem/1094

문제

• 64cm 막대기를 반씩 자른다, 막대가 2개면 더 짧은 것은 반으로 자른다.
• 위에서 자른 막대 절반 중 하나를 버리고 남은 막대들의 길이의 합이 X보다 크다면, 위에서 자른 막대 중 하나를 버린다.
• 위 과정을 반복한다.
• X가 주어졌을 때 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하라

입력

• 첫째 줄에 X가 주어진다.

출력

• 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 출력한다.

풀이

결국 이 문제에서의 요점은 64라는 값과 반으로 자른다는 사실이다. 자를 수록 막대의 길이는 64 32 16 8 4 2 1 이런 식으로 줄어들 것이고 X의 길이보다 남은 막대의 합이 크면 자른 절반을 버리기 때문에 결국 X를 넘기지 않는 범위가 될 때까지 길이는 계속 절반으로 줄어들게된다. 만약 자른 막대를 버렸을때 X를 넘기지 않는다면 더 이상 버리지 않고 자른 막대 하나를 남겨둔체, 다른 막대를 반으로 쪼개기 시작한다. 이렇게 글로 길게 쓰면 이해하기 어렵지만 결국 이 문제의 요지는 쉽게 말해 길이 X를 2진법으로 표현하는 것과 다름이 없다.

• 자른 후 자른 막대를 버렸을때 X를 넘기지 않는다는 것은 맨 앞의 비트를 찾았다는 것을 의미한다.
• 막대를 자르면 32, 16, 8, 4, 2, 1이고 막대의 합이 X를 넘기지 않도록 막대를 버리면 남은 막대의 수를 구할 수 있다.
• 즉, 위 5개의 숫자로 X를 만들어야한다는 것이고 이는 X를 이진법으로 표현했을때 1비트의 수라고도 생각할 수 있다.

X를 2진수로 바꾼 후 1의 갯수를 세기만 하면 되는 문제이다.

파이썬은 bit 함수로 2진수로 변하는 내장함수를 제공하지만 이때 2진수 앞에 0b 가 붙어 2진수라는 것을 표시한다. 우리는 2진수만을 얻기위한 것이라 해당 부분을 제거했지만 실제로 문자열로 바꿔 1의 개수만 카운트해줄 것이기 때문에 제거하지 않아도 결과는 똑같다.

따라서, 해당 문제는 입력으로 들어온 X를 2진수로 바꾼후, 해당 2진수의 1의 수를 세는 코드를 작성하여 구현할 수 있다.

코드

print(str(bin(int(input())))[2:].count("1"))