[Daily 코테] 백준 1094번: 막대기

https://www.acmicpc.net/problem/1094

1094번: 막대기

 

문제 해석

번역된 문제라 그런지 설명이 이해가 되지 않아, 설명보다는 예시를 보면서 문제를 이해했다.

지민이에게 처음에 64cm 짜리 막대가 하나 주어진다. 이 막대를 잘라서 원하는 길이의 막대기를 만들면 된다. 당연히 64cm보다 긴 막대는 만들지 못 한다.

이때 막대는 절반씩 밖에 자르지 못 한다. 예를 들어, 23cm짜리 막대기를 가지고 싶다고해서 한 번에 64cm짜리 막대기를 23cm로 자를 수 없다는 뜻이다.

대신 64cm를 절반으로 잘라 32cm 짜리 막대기 두개를 만들고, 그걸 또 잘라서 16cm, ... 이런 식으로 반복해서 잘린 막대기들을 조합해서 23cm (=16 + 4 + 2 + 1) 짜리 막대기를 붙여서 만들면 된다.

괄호 안에 적었듯이 23cm 막대기는 각각 16cm, 4cm, 2cm, 1cm 막대기, 총 4개의 막대기를 붙여서 만들 수 있으므로 답은 4이다.

First Try🎉

pole = int(input())
#lengths = [64,32,16,8,4,2,1]
n = 64
count = 0
while pole != 0:
    if pole < n:
        n /= 2
    else:
        count += 1
        pole -= n
print(count)

pole이라는 변수에 만들고 싶은 막대기의 길이(X)를 입력받는다.

처음 막대기는 항상 64cm이므로 변수 n에 64를 저장해둔다.

막대기를 붙일 때마다 count에 1씩 더해줄 것이다.

처음 입력받은 pole에서 자른 막대기의 길이를 빼줄 것이다. 계속해서 빼다보면 0이 될 것이다. 그때 while문은 멈춘다.

while문 안에 if문은 내가 갖고 있는 막대기 n이 원하는 길이인 pole보다 큰 경우를 의미한다. 내가 원하는 길이보다 n이 더 크면 반으로 나누어주면 된다.

작거나 같아질 때까지 2로 나누다가 작거나 같아지는 순간 count를 세고, 만들고 싶은 길이인 pole에서 해당 값을 빼준다.