[Python] 15652 N과 M(4)

• 문제
• 입력
• 출력
• 문제 풀이
  • A. 접근

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

출력

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

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

문제 풀이

A. 접근

백트래킹을 통해 수열을 구하는 문제. 백트래킹이 조금 약해서 N과 M 문제를 다 풀어보고자 한다.

더보기

N과 M 문제에서 백트래킹은 재귀 구조를 사용하며 해를 찾아간다. DFS와 연관이 있다. 트리에서 깊이 먼저 탐색하는 것과 유사하다.
여기서 N과 M의 포인트는 비내림차순이며 중복을 허용한다는 점이다.

보통 백트래킹으로 수열을 찾거나 순서를 찾는 문제에서는 이러한 구조가 종종 쓰인다.

ans.append(num[i])
backtracking(n + 1)
ans.pop()

더보기

이렇게 깊게 먼저 탐색한 후에 부모 노드로 다시 간 다음 다른 노드로 가는 그런 구조이다.

미로를 탐색한다고 할 때, 갈림길에서 왼쪽으로 갔다가 길이 막히면 다시 나와서 오른쪽 길로 다시 가는 그런 느낌이다.

중복을 허용하지 않는다면 방문 테이블을 만들어두는 것이 좋다. 그런데 이것은 중복을 허용하기 때문에 따로 방문테이블을 만들지 않았고, 비내림차순이기 때문에 정렬을 해주어 문제를 풀었다.

B. 코드 분석

전체 코드

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

arr = [i for i in range(1, n + 1)]

ans = []

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

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

solve(0, 0)

B-1. 준비

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

arr = [i for i in range(1, n + 1)]

ans = []

수를 입력 받아 배열을 만들어주고, 출력 때 사용할 리스트로 ans를 만들었다.

B-2. 풀이

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

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

solve(0, 0)

cnt는 수열의 길이이다. 수열의 길이가 문제의 조건을 만족하면 Unpacking을 통해 출력한다.

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

for 반복문에서 range의 인자로 idx를 설정하였다. 이후 다시 idx 자리에 i를 삽입했다. 이것은 비내림차순을 위해 설정했다. 이렇게 하여 idx 이전은 고려하지 않고 같거나 큰 값만 수열에 추가되게 된다.

총평

백트래킹은 항상 발목을 잡았었는데 슬슬 잘 풀린다.