문제설명 입출력 예제 개념 이 문제는 64cm 막대기를 이용하여 길이가 Xcm인 막대기를 만드는 문제다. 이때, 우리가 사용할 수 있는 도구는 막대기를 정확히 절반으로 자르는 것뿐이다. 따라서, 가능한 막대기의 길이는 64, 32, 16, 8, 4, 2, 1cm 등 2의 거듭제곱 형태다. 이는 우리가 풀려고 하는 문제를 이진수 표현으로 해석하는 키가 된다. 각 이진수의 자리는 2의 거듭제곱을 나타내며, 우리가 필요한 막대의 개수는 이진수 표현에서 1의 개수와 같다. 이는 막대기를 사용하느냐, 사용하지 않느냐를 이진수의 1과 0으로 표현한 것과 같다. 이런 점에서 볼 때, 이 문제는 그리디 알고리즘을 사용하여도 풀 수 있다. 그리디 알고리즘을 사용하는 경우, 가장 큰 막대부터 시작하여 목표 길이를 초과하지..
