15651 N과 M (3)

💡문제 분석 요약

• N, M 값을 받고 1 ~ N까지의 숫자중에서 M개의 숫자를 중복 허용하여 출력한다.
• 오름차순으로 출력한다.

💡알고리즘 설계

• 이전에 풀었던 N과 M(9) 문제처럼, DFS를 이용한다.
• m개의 원소가 모이면 print해주는 탈출조건을 작성해준다.

💡코드

n, m = map(int, input().split())
s = []

def backTracking(): # DFS를 이용함
    if len(s) == m: # m개가 모였다면 출력
        print(*s)
        return
    for i in range(1, n+1): # m개의 숫자가 모이는 과정인데, prev를 통해 중복 출력을 방지함.
        s.append(i)  # 1~n까지 값을 넣는 것이기 때문에 굳이 list 초기화 하지 않아도 됨
        backTracking()
        s.pop()


backTracking()

💡시간복잡도

• 중복을 포함하므로 실제 출력해보면 O(N^M)이 됨을 알 수 있었다.

💡 틀린 이유

• vistied를 지우지 않고 그대로 사용해서 틀렸다. 이번 문제는 중복을 허용하기 때문에 visitied를 오히려 쓰면 안되는 문제였다.

💡 틀린 부분 수정 or 다른 풀이

• visited 삭제하고, 재귀 실행 조건을 삭제함. (for문 내에서 항상 재귀)
• 1~n까지 N개의 원소를 담는 list를 선언하지 않고 for문으로 1부터 N까지 값을 바로 append 해주는 방식으로도 진행할 수 있었다.

💡 느낀점 or 기억할정보

• 백트래킹의 탈출 조건을 항상 생각하면서 언제 append하고 언제 pop 하는지, 그리고 그 사이 백트래킹 재귀는 어디로 들어가야하는지 코드 "순서"를 잘 짜야한다.