[CodingTest] 파이썬 백준 #15651 N과 M (3) / 중복순열 product, 중복조합 combinations_with_replacement

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

---

시간 초과, 메모리 초과 번갈아 나서 결국 인터넷 보고 푼 문제 ㅠ

그래도 답이 나오긴 나왔어서 내 코드도 올려본다.

 

 

내 코드 - 시간 초과 or 메모리 초과

from itertools import combinations
import sys
n,m=map(int,sys.stdin.readline().split())

arr = [i+1 for i in range(n)]*m

lst = sorted(set(combinations(arr,m)))
for i in range(len(lst)):
    print(" ".join(map(str,lst[i])))

그래도 풀이 설명을 해보자면, 예를 들어 n이 4, m이 2일 때, arr에 [1,2,3,4,1,2,3,4]와 같이 저장한다.

그리고 arr에서 m개 만큼 조합을 해주고, set로 중복 제거한 뒤 오름차순 정렬해서 출력.

아무래도 조합을 하면 일단 갯수가 너무 많아져서 7 7일 때 엄청 오래 걸리는 것 같다.

그래도 product를 몰랐어서 그렇지 ... 나름 비슷한 접근 아니었나? 하고 합리화함 ㅋㅋ 

아래에서 product로 푼 코드를 보도록 하자.

 

---

인터넷 보고 푼 풀이

from itertools import product
n,m = map(int,input().split())
arr = product(range(1,n+1),repeat = 3)

for item in arr:
    print(item)

product는 처음 알게 되었다. product는 중복 순열!! (진심 기억안남)

아래에서 개념을 살펴보자.

---

중복 순열 (product)

3개 중 2개를 중복순열로 뽑는다고 하였을 때, 뽑은 아이템을 제자리에 갖다 두고 다시 뽑는 것으로, 본(i, i)와 같은 경우도 나올 수 있다.

조합, 순열은 뽑은 두개가 달라야 한다.

예를 들면, 감자, 고구마, 밤을 중복순열로 했을 때 다음과 같은 결과가 나온다.

from itertools import product
lst = ['감자','고구마','밤']
result = list(product(lst,repeat=2))
print(result)
#result => [('감자', '감자'), ('감자', '고구마'), ('감자', '밤'), 
			('고구마', '감자'), ('고구마', '고구마'), ('고구마', '밤'), 
			('밤', '감자'), ('밤', '고구마'), ('밤', '밤')]

---

중복 조합 (combinations_with_replacement)

중복 조합도 있다. 

중복 조합은 순서 상관없이 같은 것을 똑같이 소유할 수 있으며, 어떠한 것을 소유했는지를 의미한다고 한다.

['감자','고구마','밤'] 중 2개를 중복조합 한 결과는 다음과 같다.

from itertools import combinations_with_replacement
arr = ['감자', '고구마', '밤']
result = list(combinations_with_replacement(arr, 2))
print(result)

#result => [('감자', '감자'), ('감자', '고구마'), ('감자', '밤'), 
			('고구마', '고구마'), ('고구마', '밤'), 
            ('밤', '밤')]

---

이거 말고 dfs로 푼 사람도 꽤 있던데 아직 공부하지 않았으므로 ㅠ 공부할 때 다시 들러 풀어보도록 해야겠다.

재귀로 푼 사람도 있던데 재귀는... 나는 너무 어려워 ㅠㅠ