[Python] 15656 N과 M(7)

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

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

문제 풀이

A. 접근

같은 수를 여러 번 선택할 수 있는 수열 문제.

백트래킹으로 간단하게 구현할 수 있다. 라이브러리를 사용하는 간단한 방법이 있지만, 다양한 코딩에 익숙해지는 것이 좋다고 생각해서 백트래킹을 사용한다.

원하는 깊이까지 도달했을 때, 출력하는 DFS 방식과 유사하게 풀이한다.

B. 코드 분석

전체 코드

n, m = map(int, input().split())
arr = sorted(map(int, input().split()))

ans = []

def solve(cnt):
    if cnt == m:
        print(*ans)
        return

    for i in range(n):
        ans.append(arr[i])
        solve(cnt + 1)
        ans.pop()

solve(0)

B-1. 준비

n, m = map(int, input().split())
arr = sorted(map(int, input().split()))

ans = []

사전 순서대로 출력을 해야 해서 미리 정렬을 해둔다.

B-2. 풀이

def solve(cnt):
    if cnt == m:
        print(*ans)
        return

    for i in range(n):
        ans.append(arr[i])
        solve(cnt + 1)
        ans.pop()

solve(0)

문제에서 원하는 m까지 수를 선택했으면 출력한다.

ans 배열에 값을 추가하고, cnt를 높여 다시 solve 함수를 실행한다. 앞서 cnt가 m까지 출력이 됐으면 ans.pop() 부분으로 넘어가서 수열을 다시 출력한다.

총평

백트래킹의 전반적인 과정을 이해하고 활용하는 데에 좋은 문제인 것 같다.