Jacob's Coding Playground

[문제 출처 : Codechef] 두근거리는 마음으로 소개팅 자리에 나갔습니다. 그녀는 의외로 푸드코트에 가서 식사하기를 원했고, 메뉴판은 다음과 같이 구성되어 있었습니다.

그녀는 소개팅 자리였기 때문에 많은 메뉴를 먹는 것을 원하지 않았습니다. 하지만 그래도 남자는 소개팅을 위해 p의 돈을 가지고 나왔기 때문에, 그 돈을 모두 사용하려고 합니다. p로 살 수 있는 가장 적은 메뉴의 수는 몇개일까요? (참고로 같은 메뉴를 두 번 주문하더라도 두 개의 메뉴가 주문된 것으로 간주합니다.)

많은 분들이 알아차리셨겠지만, 가격들이 2의 배수 형태로 증가하는 것을 확인할 수 있습니다. 결국 2048보다 큰 p에 대해서는 2048로 살 수 있을 때까지 산 후, 2048보다 작은 나머지를 이진수로 변환하여 1의 숫자를 count해 주시면 되겠습니다.

꼭 이진수가 아니더라도, 당연히 가능한 가장 높은 가격들로 우선 채워나가면서 p를 채우는 것이 가장 적은 메뉴를 주문하는 방법이 되겠습니다.

def minNumOfMenus(p):
    minimum = 0
    if p >= 2048: #2048보다 큰 p의 경우,
        minimum += p/2048 #2048짜리 메뉴를 살 수 있을 만큼 사고,
        p = p % 2048 #그 나머지를 구합니다.
    while p > 0: #2048보다 작은 나머지 부분은 계속해서 2로 나눠가면서 이진수의 1들을 세어 줍니다.
        minimum += p % 2
        p = p / 2
    return minimum

>>> print minNumOfMenus(10)
2
>>> print minNumOfMenus(256)
1
>>> print minNumOfMenus(255)
8
>>> print minNumOfMenus(4096)
2

결과가 잘 나오네요 :) 이런 소개팅은 없겠지만, 어쨌든 문제는 해결했네요 ^^;