[백준 15652] 백트래킹2와 itertools

전 문제(15651)에서 검색을 통해 나름 공부했다고 생각했는데 아니었나보다.

조건 하나만 추가된 건데, 정답률도 80% 이상인데 나는 풀지 못했다.

 

>방법1

a,b = map(int, input().split())
l = []

def back(a,b,i=0,t=0):
    if b==i:
        print(*l)
        return 
    for j in range(t,a):
        l.append(j+1)
        back(a,b,i+1,j)
        l.pop()
back(a,b)

 

15651과 달리 인자 t가 추가되었고 DFS방식을 이용해 해결하는 것이었다.

그래서 append와 pop이 추가되었다.

그리고 다른 사람의 정답들을 보면서 itertools의 또 다른 유용한 함수를 배웠다.

 

> 방법2

from itertools import combinations_with_replacement
a,b = map(int,input().split())

for i in combinations_with_replacement(range(1, a+1), b):
    print(*i)

 

combinations_with_replacement는 이 문제에서 원하는 답을 그대로 준다.

예시로 'ABCD'를 repeat=2로 주면 AA AB AC AD BB BC BD CC CD DD 이렇게 조합을 만들어준다.

 

아래는 python docs에서 가져온 내용이다. product나 combinations_with_replacement 외에 두 개가 더 있다.

 

product()	p, q, … [repeat=1]	데카르트 곱(cartesian product), 중첩된 for 루프와 동등합니다
permutations()	p[, r]	r-길이 튜플들, 모든 가능한 순서, 반복되는 요소 없음
combinations()	p, r	r-길이 튜플들, 정렬된 순서, 반복되는 요소 없음
combinations_with_replacement()	p, r	r-길이 튜플들, 정렬된 순서, 반복되는 요소 있음

예시 결과

product('ABCD', repeat=2)	AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)	AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)	AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2)	AA AB AC AD BB BC BD CC CD DD