[BOJ] 15649 N과 M (1) Python

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

15649번: N과 M (1)

N과 M (1)

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

83493

52756

34348

62.392%

문제

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

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

입력

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

출력

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

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

 

풀이 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
visited = [False]*(n+1)
answer = []
def rec(depth, n, m):
    if len(answer) == m:
        print(' '.join(map(str, answer)))
        return

    for i in range(1, n+1):
        if not visited[i]:
            visited[i] = True
            answer.append(i)
            rec(depth+1, n, m)
            visited[i] = False
            answer.pop()

rec(0, n, m)

6개월 전에 정답 참고해서 풀었던 백트래킹 문제이다.

아직 백트래킹 이해도가 많이 부족하다. N과 M 시리즈 다 풀자!

 

방문처리, 깊이로 종료조건 설정, 재귀

구조 익히고, 원리를 이해해야 하는데 아직 반복문-재귀 부분 원리를 정확하게 이해를 못한 것 같다.

문제를 더 많이 풀어봐야겠다.