[ 입력 ]
- 첫째 줄에 만들 막대기의 길이 X 입력
( X ≤ 64, 자연수 )
[ 출력 ]
- 필요한 막대기의 수 출력
이 문제의 중요 point는 처음 가지고 있는 막대기가 64cm이고, 절반으로 나눈다는 것이다.
막대기를 절반으로만 나눠 사용 가능하므로, 사용할 수 있는 막대기의 길이는
1 2 4 8 16 32 64
이렇게 7가지만 사용 가능하다.
수를 이진수로 생각할 수 있다면 매우 간단하게 해결된다.
내가 만들 수 X를 이진수로 변환한 후 1의 개수를 구하면 그 값이 X cm 의 막대기를 만들 때 필요한 막대기의 개수가 된다.
< ex >
- 64 cm -> 0100 0000 이므로 1개
- 33 cm -> 0010 0001 이므로 2개
따라서 이 문제는 입력받은 X를 이진수로 변환해 1의 개수를 출력하면 해결된다.