[백준 알고리즘 #1094] 막대기(Python3)

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

1094번: 막대기

---

---

정답 코드 #1

def div():
    half = int(stick[-1] / 2)
    stick[-1] = half
    
    if sum(stick) < X:
        stick.append(half)
        
    return stick

X = int(input())
stick = [64]

while sum(stick) != X:
    if sum(stick) > X:
        stick = div()

print(len(stick))

문제 풀이 #1

정답 코드 #1은 문제에 제시된 방법 그대로 구현한 정답이다. 막대를 자르는 작업을 div() 함수로 구현하였다.

 

우선 막대들을 나타내는 리스트 형의 stick에는 처음 64cm인 막대가 1개 저장되어 있다.

문제가 종료되는 시점은 가지고 있는 막대들의 합이 X와 같아지는 순간이므로 while를 통한 반복문을 구현하였으며, 막대를 자르는 조건인 막대들의 길이의 합 sum(stick)가 X 보다 큰 경우 막대를 자르는 div() 함수를 실행시킨다.

 

div 함수에는 기본적으로 제일 짧은 막대를 반으로 나누는 과정을 거치며, 만약 자른 막대 중 하나를 버리고 남은 막대의 길이의 합이 X 보다 크거나 같다면, 자른 막대 중 하나를 버리는 과정을 역으로 생각하여 stick[-1]을 우선 반으로 나눈 다음에 만약 막대 길이의 합이 X 보다 작은 경우에 제일 짧은 길이의 막대를 append 해 주었다.

 

그리고 막대 길이의 합이 X와 같아져서 반복문이 종료되면, stick의 갯수를 len()를 이용해서 구하고 출력했다.

 

정답 코드 #2

X = int(input())
cnt = 0

while X != 0:
    if X % 2 == 1:
        cnt += 1
    X = X // 2
    
print(cnt)

문제 풀이 #2

정답 코드 #2는 비트 마스킹을 활용한 문제 풀이이다.

비트 마스킹은 비트(bit)를 활용한 풀이 기법이다.

 

비트에 초점을 맞추면 위의 문제는 결국 주어진 X를 2진수로 표기하였을 때, 1의 개수를 출력하는 문제이다.

 

예를 들어 23을 2진수로 표기하면 10111로 1은 총 4개가 있고. 32를 2진수로 표현하면 100000으로 1은 1개가 있다.