N과 M -(2) [문제번호 : 15650] (Python 파이썬 풀이)

문제 [15650]

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

• 예제 입력 1
  3 1
• 예제 출력 1
  1
  2
  3

• 예제 입력 1
  4 2
• 예제 출력 1
  1 2
  1 3
  1 4
  2 3
  2 4
  3 4

• 예제 입력 1
  4 4
• 예제 출력 1
  1 2 3 4

문제 해석

앞에서 풀어보았던 문제와 비슷하나 이번에는 사용된 문자 그 다음부터를 출력해야 한다. 이전과 같은 초기값들을 설정해주고 시작하자. 초기값 설명은 이전에 리포팅한 15649문제에서 확인할 수 있다.

N,M = map(int,input().split())
List = []
for i in range(N):
    List.append(i+1)
use_check = [True] * N
Answer= [0 for _ in range(M)]

그리고 이전과 같이 사용한 숫자를 append시키고, 출력이후에 pop을 시킨다. 차이점이 있으면 첫번째 값을 완전히 사용하고 난 이후에 그 값은 계속해서 False로 두어야 한다는 것이다. 그래서 i번째 값을 pop을 시킨 이후에 i 다음의 값들은 전부 True로 바꿔준다. 즉 아래와 같은 작업을 한다.

def bubun(idx):
    global use_check,Numbers
    if idx==M:
        print(*Numbers)
        return
 
    for i in range(idx,N):
        if not use_check[i]:
            continue
        use_check[i] = False
        Numbers.append(List[i])
        bubun(idx+1)
        Numbers.pop()
        for j in range(i+1,N):
            use_check[j] = True # i번째 값을 False로 위에서 바꾼 뒤 i+1부터는 다시 사용하기 위해 전부 True로 바꿔준다.

마지막으로 bubun함수를 출력해보자. bubun은 idx 값이 0부터 시작하기 위해서 bubun(0)으로 출력한다. 끝으로 코딩 작성한 것을 공개하고 마무리합니다.

N,M = map(int,input().split())
use_check = [True] * N
Numbers = []
List = []
for i in range(N):
    List.append(i+1)
 
 
def bubun(idx):
    global use_check,Numbers
    if idx==M:
        print(*Numbers)
        return
 
    for i in range(idx,N):
        if not use_check[i]:
            continue
        use_check[i] = False
        Numbers.append(List[i])
        bubun(idx+1)
        Numbers.pop()
        for j in range(i+1,N):
            use_check[j] = True
bubun(0)

출처

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

15650번: N과 M (2)