백준 1094 막대기 (파이썬)

아이디어

1. 일단, 문제를 이해하기가 어렵다.
2. 대충 막대기를 반으로 짜르고 가지고 있는 막대의 길이의 합이 원하는 숫자가 나올 때, 막대기는 몇개냐 라고 해석함.
3. 비트 연산자를 이용해 경우의 수를 가지고 해봤더니, 맞았다.

---

풀이 및 해설(주석)

N = int(input())

# 일단 64길이의 막대가 있으니, 잘라서 만들 수 있는 막대기의 길이를 다 넣어줬다.
stick = [64, 32, 32, 16, 16, 8, 8, 4, 4, 2, 2, 1, 1]

for i in range(1<<len(stick)):  # 비트 연산자를 활용해 경우의 수를 확인해본다.
    sums = 0; count = 0         # sums는 n개의 막대가 나올 때 길이의 합, count는 갯수
    for j in range(len(stick)):
        if i & (1<<j):          
            sums += stick[j]    # 더해주고 카운트해준다.
            count += 1
    if sums == N:               # sums이 N과 같아진다면, 그 갯수를 출력한다.
        print(count)
        break