[python_파이썬_Pass]백준_15652번_N과 M(4)_백트래킹_풀이

공부하는허딩크 : https://www.youtube.com/live/Q8BKRFH8mW0?feature=shared

이번에도 itertools와 재귀함수를 활용해서 해결해보자

 

<첫번째 시도 : itertools활용>

라이브러리를 활용하면 정말 깔끔한 코드가 만들어 진다.

import sys

from itertools import combinations_with_replacement as cwr

input = sys.stdin.readline

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

nums = list(i for i in cwr(range(1, N + 1), M))

for num in nums:

    print(*num)

 

<두번째 시도 : 재귀함수 활용>

cwr([], 조건)을 어떻게 줄까 조금 고민했으나 중복이 허용되므로 i로 조건을 걸었다.

import sys

input = sys.stdin.readline

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

def cwr(seq, start):

    if len(seq) == M:

        print(*seq)

        return

   

    for i in range(start, N + 1):

        cwr(seq + [i], i)

cwr([], 1)

 

<세번째 시도 : depth를 활용>

import sys

input = sys.stdin.readline

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

answer = []

def cwr(depth, start):

    if depth == M:

        print(*answer)

        return

   

    for i in range(start, N + 1):

        answer.append(i)

        cwr(depth + 1, i)

        answer.pop()

       

cwr(0, 1)

 

백트레킹 문제인 것을 알고 보니까 쉽게 해결할 수 있다. 조금 더 연습을 해서 내것으로 만들어야 겠다.