백준 15650번: N과 M (2) (S3) - Python 풀이

문제 설명

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

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

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

입력

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

출력

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

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

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

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

예제 입력 3

4 4

예제 출력 3

1 2 3 4

문제 요약) N과 M (1)과 다른 점은 예제 입력 2를 보면 한눈에 알 수 있다.

풀이 과정

N과 M (1)과 일단 똑같이 구현하고, 조건이 하나 추가된 문제입니다.

예제 입력 2의 결과를 보면 2 1도 없고 4 1, 4 2와 같은 값도 출력되지 않고 있습니다. 1 2, 1 4, 2 4와 같은 수열이라고 판단하는 거죠. 그렇기 때문에 이런 케이스들은 출력을 안 해주면 됩니다.

1 2, 1 4, 2 4는 통과하는데 2 1, 4 1, 4 2는 통과 안 되는 조건문은? 바로 오름차순 정렬 전과 후의 차이점이 있는가/없는가 로 이를 구분할 수 있습니다. 1 2, 1 4, 2 4는 오름차순 정렬을 해도 똑같지만, 2 1, 4 1, 4 2는 오름차순 정렬을 하면 1 2, 1 4, 2 4가 되어버립니다. 이 케이스를 재귀 종료 조건 안에 넣어서 출력에 제한을 걸어줍니다.

정답 코드

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

numbers = []

def backtracking():
    if len(numbers) == M:
        # numbers를 오름차순 정렬한 상태가 원래 numbers랑 같을 때에만 출력
        if sorted(numbers) == numbers:
            print(*numbers)
        return
    for i in range(1, N+1):
        if numbers.count(i) == 0:
            numbers.append(i)
            backtracking()
            numbers.pop()

backtracking()

이상입니다.

+

N, M = map(int, input().split())
numbers = []

def backtracking(k):
    if len(numbers) == M:
        print(*numbers)
        return
    for i in range(k, N+1):
        if numbers.count(i) == 0:
            numbers.append(i)
            backtracking(i+1)
            numbers.pop()

backtracking(1)

이렇게 for문 도는 시작 지점을 i+1부터 해서 이전 값은 아예 돌지 않게 하는 방법도 있습니다.