[알고리즘 문제] tobin (Python / 파이썬)

문제

두 정수 n, k를 입력받아 k개의 1을 가진 n자리 이진 패턴을 출력하는 프로그램을 작성하세요.

입력

두 정수 n, k가 입력으로 주어진다. ( 0 < n <= 30, 0 <= k < 8 , n >= k )

출력

결과를 내림차순으로 출력한다.

---

문제 풀이

k개의 1을 가진 n 자리 이진 패턴을 구해 내림차순으로 출력하는 문제입니다.

먼저 구한 n 자리 이진 패턴을 저장하기 위해 array 배열을 만들어줍니다.

여기서 주의 할 점은 결과를 내림차순으로 출력해야 한다는 것 입니다. 

즉, 큰 수부터 출력 되도록 해야 하므로 1이 먼저 삽입되도록 해야합니다. 

따라서 array에 먼저 1을 삽입해주고 그 다음 index와 1을 사용했으므로 

count를 1 증가시켜 재귀함수를 실행해줍니다. 

그 다음엔 0을 삽입해주고 그 다음 index와 count를 넘겨 재귀함수를 실행해줍니다.

만약 count가 k보다 커졌다면 이미 1을 k 보다 더 많이 사용했다는 것이므로 

더 탐색할 필요가 없습니다. 따라서 return을 해줍니다.

만약 index가 n이 됐다면 n자리를 만들었다는 것이므로 count가 k인지 확인합니다.

만약 k라면 원하는 답이므로 출력해줍니다.

---

My Code

n, k = map(int, input().split())

array = [0] * 50

# k개의 1을 가진 n자리 이진 패턴을 출력할 함수
def binary(index, count):
    if count > k: # 1이 k개보다 많아지면
        return    # 더 탐색할 필요 없음
    if index == n: # n자리라면
        if count == k: # 1의 개수가 k인지 확인
            # 맞다면 출력
            for i in range(n):
                print(array[i], end = '')
            print()
        return 

    # 내림차순으로 출력하기 위해 1먼저 삽입
    array[index] = 1
    binary(index + 1, count + 1) # 다음 인덱스, 1의 개수 증가시켜 넘겨줌
    array[index] = 0            
    binary(index + 1, count)     # 다음 인덱스, 1의 개수 그대로 넘겨줌

binary(0, 0)