백준 (boj) 파이썬 - 1094 막대기

문제링크 : https://www.acmicpc.net/problem/1094

1094번: 막대기

 

뭔가 생각 못한 반례가 있을거라는 느낌이 있었지만, 없었다. 문제 그대로 구현만 하면 정답이었다.

64를 반으로 자르고 잘라서, 주어진 x길이를 만드려면, 몇개를 이어붙어야 하는가였다.

시작부터 64의 약수들을 list 안에 넣어놓고,  x보다 작은 요소들을 빼가면서 카운팅하는식으로 코딩했다.

x = int(input())
arr = [64]; temp =64; cnt = 0

for i in range(6):    #64들의 약수들을 구하는 for문
    temp//=2
    arr.append(temp)
    
if x in arr :       #arr 안에 있는 수가 x라면, 이어붙일 필요없이 1을 출력.
    print(1)
else :
    for q in arr :  #arr의 큰 요소부터 붙이는 식으로, for문 작성
        if x >= q :
            x -= q
            cnt +=1
    print(cnt)