백준 15649번: N과 M (python, 파이썬)

• 문제

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

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

---

• 입력

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

---

• 출력

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

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

---

• 코드

N, M = map(int, input().split(' '))

# 숫자 사용 여부 확인
# Check number is used
check = [False]*(N)

# 정답 배열
# answer list
answer = [0]*M

def dfs(idx):
    # idx값이 증가하다가 정답 배열의 길이가 M에 도달하면 답 출력
    # When idx value increases then length of the answer list reaches M, then print answer
    if idx == M:
        for i in range(M):
            print(answer[i], end=' ')
        print()
        return

    # M에 도달하지 못하면 가능성 있는 숫자 계속 찾기
    # If not reached M, continuously find the possible number
    for i in range(N):
        # 이미 해당 숫자가 사용되었으면 pass
        # Pass if the number already been used
        if check[i]:
            continue

        # 숫자가 사용되지 않았으면 정답 배열에 기록하고 True로 바꾸어준다
        # If the number not used, then record answer list and change values from false to true
        check[i] = True
        answer[idx] = i+1

        # 재귀 호출
        # Call recursive
        dfs(idx+1)

        # 재귀가 끝나면 다시 되돌아갈 때 사용하지 않았던 상태로 되돌려주기
        # Return to unused state when recursive is finished
        check[i] = False

dfs(0)

재귀함수의 가장 기본적인 문제로 풀기에 좋은 문제이다.

숫자를 나열하는 모든 경우의 수를 생각하면 되는데 check라는 list를 통해 사용이 되었는지 아닌지 확인해주면 된다.

 

아마 이렇게 글만 작성하면 처음 접하는 사람들은 이해를 못할것 같아서 아래의 예시를 통해 코드를 이해하면 편할 것 같다.

 

N=4, M=2

 

 

---

• 출처

www.acmicpc.net/problem/15649