파이썬, 가능한 N자리 이진수 경우의 수 (백트래킹 이용)

파이썬,  가능한 N자리 이진수 경우의 수 (백트래킹 이용)

 

글. 오상문 sualchi@daum.net 

 

 

가능한 이진 수 경우 수를 구하는 문제입니다.  
단, 0이 연속되는 경우는 제외해야 합니다.

가능한 3자리 이진수는 다음처럼 8가지 입니다.

000, 001, 010, 011, 100, 101, 110, 111 

 

그런데 0이 연속된 경우를 빼면 5가지이다. 즉, 문제에서 3자리인 경우는 5가 정답니다.
010, 011, 101, 110, 111 

 

예제 코드는 다음과 같습니다. 

count = 0

def solution(n, bit):  # n개 자리, bit 값
    global count 
    if n == 0:         # 끝자리까지 왔으면 경우 1 증가 
        count += 1
        return
    solution(n-1, 1)   # 다음 1 검사는 무조건 진행 
    if bit == 1:       # 다음 0 검사는 현재 1인 경우만 호출 (가지치기)
        solution(n-1, 0)

#-------- main ---------------

N = int(input())
solution(N, 1)  # 시작은 1 설정(처음엔 1이나 0 모두 올 수 있으므로) 
print(count)    # 3을 입력하면 5 출력

 

<이상>