[BOJ / 파이썬] 11652: N과 M (4)

2021.10.09 - [문제풀이/BOJ] - [BOJ / 파이썬] 15649: N과 M (1)

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

단계 : 백트래킹

알고리즘 분류 : 백트래킹

 

풀이: 

N과 M의 마지막 문제이다. N과 M 두번째 문제와 세번째 문제를 합쳐놓은 문제이다. 기존 N과 M 1번 문제와 다른 점은 숫자를 고를 때 중복이 가능하나 비내림차순이어야 한다는 점이다. 내림차순으로만 안 고르면 된다는 뜻이므로 이 점만 유의하여 범위를 다시 설정해주면 된다.

 

기존 N과 M 풀이는 아래 내용 참조

2021.10.09 - [문제풀이/BOJ] - [BOJ / 파이썬] 15649: N과 M (1)

N과 M (3)과 같이 중복을 생각할 필요가 없으니 visited 사용부를 모두 제거해준다. 나 같은 경우 기존 N과 M 코드에서 visited를 삭제하려고 하니 인덴트(들여쓰기) 고쳐야 하는게 귀찮아서 visited의 값을 바꿔주는 부분만 코드에서 지웠다. 비내림차순을 위해서 일단 이전 값보다 작은 값이 나오면 안되니 N과 M(2) 와 같이 for문을 시작할 범위를 함수의 요소로 함께 넘겨준다. 마지막에 result 리스트에 넣어준 값이 한번 더 나와도 내림차순이 아니니 요소로 넘겨줄 때 마지막에 리스트에 넣어준 값을 그대로 다음 함수에 넘겨준다. 그렇게 되면 for문의 범위가 내림차순이 나올 수 없는 구조가 된다.

 

코드

import sys


def solve(d, s, n, m):
    if d == m:
        print(" ".join(map(str, result)))
        return
    for i in range(s, n):
        if visited[i] == False:
            result.append(i + 1)
            solve(d + 1, i, n, m)
            result.pop()


n, m = map(int, sys.stdin.readline().split())

visited = [False] * n
result = []
solve(0, 0, n, m)