[BOJ/python] 18409번 막대기

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

1094번: 막대기

문제 해석

​

첫 번째 줄에 만들고 싶은 막대의 길이를 입력한다. 단, 막대의 길이는 64 이하의 자연수이다.

이후 몇개의 막대를 붙여야 막대를 만들 수 있는지 출력한다.

---

코드

count = 0
stick = 64
a = int(input())

while True:
    if a == stick:
        count +=1
        break
    else:
        stick = stick / 2
        if stick < a:
            count +=1
            a = a - stick

print(count)

---

문제 풀이

​

사용할 수 있는 문자가 1, 2, 4, 8, 16, 32, 64이면, 만들 수 있는 수는 127까지이다.

그러나 우리가 만들고 싶은 막대는 길이가 64 이하이므로 1부터 64까지 모두 만들 수 있다고 생각하면 된다.

​

문제 번호의 일부인 18과 40을 예로 들어보자.

​

18의 경우 64로 만들지 못하므로 2로 나눈다.

32 역시 18을 만들 수 없으므로 2로 나눈다.

16은 18보다 작으므로 18에서 16을 빼주고, count에는 1을 추가한다. 남는 막대의 길이는 2다.

위 과정을 반복하면 2가 되고, count에 1이 더 추가돼서 16 + 2, 2개로 만들 수 있다는 걸 확인할 수 있다.

​

40의 경우 64로 만들지 못하므로 2로 나눈다.

32는 40보다 작으므로 40에서 32를 빼주고, count에는 1을 추가한다. 남는 막대의 길이는 8이다.

위의 과정을 반복하면 8이 되고, count에 1이 더 추가돼서 32 + 8, 2개로 만들 수 있다는 걸 확인할 수 있다.

​

위와 같은 방법을 통해 문제를 해결할 수 있다.

---

친구가 바이너리 게임(2진수로 특정 숫자를 만들거나 맞추는 게임)을 보내줬는데, 우연찮게 이 문제를 풀고있어서 올려보았다.

재미있으니 심심하면 한 번 해보는 것도 괜찮을 것 같다.

https://learningcontent.cisco.com/games/binary/index.html

Binary Game