[🥉2 / 백준 10829 / 파이썬] 이진수 변환

 

10829번: 이진수 변환

문제

자연수 N이 주어진다. N을 이진수로 바꿔서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000)

출력

N을 이진수로 바꿔서 출력한다. 이진수는 0으로 시작하면 안 된다.

 

예제 입력  53

예제 출력  110101

 

풀이

 

십진수 N을 이진수로 변환하는 문제이다.

 

사실 bin 함수를 쓴다면 바로 이진수가 출력되긴 하지만,

재귀 카테고리에 존재하는 문제인 만큼 재귀로 풀도록 하자.

 

우선, 이진수를 변환하는 방법을 알아야 한다.

 

N이 6이라고 가정해 보자.

6%2는 0이다. 6을 2로 나눈 몫인 3을 다시 2로 나누어주자.

3%2는 1이다. 3을 2로 나눈 몫인 1을 다시 2로 나누어주자.

1%2는 1이다.

 

이제 위에서 나온 숫자를 아래에서부터 위로 올라가며 구성하면

110이 나온다. 순서에 유의하자.

 

이러한 일련의 과정에서 재귀의 가능성을 찾아볼 수 있다.N을 나눈 몫이 0이 될 때까지 계속해서 2로 나누어주며 재귀 호출을 하면 된다.

 

def solve(r, n):
    if n == 0:
        return r
    # 재귀 탈출
    
    if n%2 == 1:
        return solve("1"+r, n//2)
    else:
        return solve("0"+r, n//2)
print(solve("", int(input())))