[Python] 백준 알고리즘 문제풀이 :: 1094번

C로는 SW Expert Academy 문제를, 파이썬으로는 백준 문제를 푼다. 각각 1일 1문제를 풀기로 했고 거의 지키고 있다. 다만 블로그 업로드는 아무래도 C를 많이 올리게 됐다. 코드도 좀 더 길고 복잡하다보니 할 말이 많아서. 오랜만에 파이썬 문제를 하나 풀린다. 막대기 문제. 본질은 이진법으로 숫자를 구현하는 문제다. 재귀를 썼다.

문제

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

풀이

import sys
 
def stickAdder(x, stick, cnt, idx):
    unit = [64, 32, 16, 8, 4, 2, 1]
    if stick+unit[idx] == x:
        print(cnt)
    elif stick+unit[idx] < x:
        stick += unit[idx]
        stickAdder(x, stick, cnt+1, idx+1)
    else:
        stickAdder(x, stick, cnt, idx+1)
 
x = int(sys.stdin.readline())
 
stickAdder(x,0,1,0)

input 대신 sys.stdin.readline() 함수를 이용하기 위해 sys를 import한다.

함수를 선언해준다. 만들어야 할 길이인 x, 현재 막대의 길이 stick, 몇 개의 막대를 썼는지를 의미하는 cnt, 그리고 2의 6승부터 2의 0승까지의 막대 배열을 참조할 idx를 파라미터로 넣어준다. 이 때 처음 stick값은 무조건 0, cnt는 1, idx는 0으로 넣어준다. 함수 내부에서 다시 함수를 호출하며 증가된 값을 넣어준다.

64 길이의 초기 막대를 매 번 반으로 자르고, 한 쪽은 버리니깐 64,32,16,8,4,2,1의 단위 막대를 unit 리스트에 넣어준다. 눈치챘겠지만 그냥 7자리의 이진수를 구현하고 그 중에 1이 몇 개 있나 출력하는 문제와 같다.

가장 큰 단위인 64부터 시작한다. 만약 stick+unit[idx], 즉 0 + 64가 목표인 x와 같다면 그냥 cnt인 1을 출력하면 된다. 아니라면? stick+unit[idx]가 x보다 작거나 큰 경우가 있다. 작다면 일단 stick에 unit[idx]를 더해준다. 그리고 더해진 stick과 1씩 증가시킨 cnt, idx를 집어넣은 stickAdder 함수를 다시 호출한다.

만약 stick+unit[idx]가 x보다 크다면 어차피 이건 못 쓰는 막대다. 버린다. 다음 unit 요소에 접근해야 하니 idx만 1 증가시켜서 stickAdder 함수를 호출한다.

결국 각 unit의 요소를 더하고, 목표인 x보다 크면 버리고 작으면 더한 다음에 다시 다음 꺼 더하고, 같으면 지금까지 더한 횟수를 리턴하는 단순한 구조다.