백준 15657번 - N과 M (8)

2023-7-16 · 1 min · 108 words · Junha | Suggest Changes

Table of Contents

백준 15657번 문제 바로가기

combinations을 이용한 풀이

python에는 중복조합에 대한 라이브러리도 가지고 있다. 바로 combinations_with_replacement 지난 N과 M (1) 해답에서 combinations만 _with_replacement를 붙여주면 간단하게 해결 가능하다.

# 입력
import sys
from itertools import combinations_with_replacement
n,m = map(int, sys.stdin.readline().split())
arr = sorted(map(int, sys.stdin.readline().split()))

# 처리
for ans in combinations_with_replacement(arr, m):
    print(*list(ans))

backtracking을 이용한 풀이

중복조합을 backtracking으로도 풀어보자! 범위 설정에만 조심한다면 간단하게 풀어낼 수 있게 된다.

# 입력
import sys
n,m = map(int, sys.stdin.readline().split())
arr = sorted(map(int, sys.stdin.readline().split()))
ans = []

# 처리
def backtrack(start=0):
    if len(ans) == m:
        print(*list(map(str, ans)))
        return
    for i in arr[start:]:
        ans.append(i)
        backtrack(arr.index(i))
        ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack)

backtrack()

Comments: