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

문제 [15649]

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

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

예제 입력1

3 1

결과

1
2
3

예제 입력2

4 2

결과

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력3

4 4

결과

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

문제 풀이

문제를 해석해 보자. 입력값으로 N과 M이 주어지고, 출력값들의 길이는 M이다. 그리고 규칙적으로 뒷자리부터 해서 점차 증가하는 결과가 나온다. 일단 리스트를 만들어 보자. 입력값 [4 2]를 기준으로 시도를 한다. 사용되는 숫자들은 1,2,3,4 이므로 List라는 이름으로 새로운 리스트를 만들고 초기값들을 설정해두자.

N,M = map(int,input().split())         #입력값 N과 M을 받는다.
List = [ x+1 for x in range(N) ]     #List는 [1,2,3,4]가 될 것이다.
use_check = [True] * N                 # 이런 문제같은 경우 사용 여부를 따지는게 풀이에 편하다.
Answer = []                         # 나중에 출력할 리스트이다.

초기값들을 설정해 두고, 이제 규칙을 찾아보자. 출력값은 1 2 로 시작하여 1 3 , 1 4를 거쳐 4 3이 나와야 한다. 즉 뒷자리부터 앞에 숫자를 제외하고 돌아가면서 사용해야 한다. 이제부터 함수를 정의해보자
함수의 이름은 bubun으로 하였고, 만약 숫자를 사용하면 그에 해당하는 인덱스값을 False로 바꿔주어 True인 애들만 사용하게 만들었다.

def bubun(idx):                        # 함수를 정의
    if idx==M:                        # idx 값을 0부터 시작해서 1개씩 올릴것이다. idx가 0인 경우 Answer의 값들을 print한다.
        print(*Answer)
        return
    else:                            # idx 값이 M이 아닌 경우
        for i in range(N):    
            if not use_check[i]:    # 만약 True가 아니면 continue를 통해 for구문으로 돌아간다.
                continue            # True 면 통과
            use_check[i] = False    # True 였던 i번째 값을 False로 변경
            Answer.append(List[i])    # i번째 값을 Answer에 붙여준다.
            bubun(idx+1)            # idx값을 1만큼 증가시켜 재실행. 처음 시도시 use_check=[F,T,T,T] , Answer = [1] 로 다시 실행된다.
            Answer.pop()            # 한 번 사용하였으면 이제 반납을 해준다.
            use_check[i] = True        # False에서 다시 True로 반납해준다.
 

이제 결과값을 확인해보자. 정의된 함수를 사용하기 위해서 bubun(0)을 아래에서 실행해보자. 그러면 우리가 원하는 결과가 나온다는 것을 확인 할 수가 있다. 이제 완성된 코드를 써보자.

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

이번 포스팅을 마치며

사용했는지 여부를 판별하는 use_check개념이 생각보다 제대로 안잡혀 있다는 것을 알았다. 다른 문제들을 풀어가면서 고쳐보도록 하겠다.

출처

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

15649번: N과 M (1)