[백준] 15649 N과 M python3

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

15649번: N과 M (1)

 

코드

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

check = [False] * (N+1)
result = [0] * M

def backtracking(idx):
    # 다 채우면
    if idx == M:
        # 출력하고 return
        print(" ".join(map(str, result)))
        return

    for i in range(1, N+1):
        if check[i]: # 이미 리스트에 있으면 넘어감
            continue

        # idx 위치에 원소 채우기
        check[i] = True
        result[idx] = i

        # 다음 인덱스 채우러 감
        backtracking(idx+1)

        # 갔다가 돌아오면
        # (?, ..., i, ...) 는 다 채운거니까 해제
        check[i] = False


backtracking(0)

 

 

해설

백트래킹을 활용해서 풀 수 있다.

원하는 자릿수(M) 크기의 리스트 result 를 만들고, 각 자릿수에 조건에 부합하는 원소를 넣는다.

중복해서 넣으면 안되므로 check 리스트에 그 원소가 체크 되었는지를 저장한다.