백준: 15652 N과 M (4)

N과 M 시리즈

• 원소가 1에서 N인 경우
  • 15649 N과 M (1)
  • 15650 N과 M (2)
  • 15651 N과 M (3)
  • 15652 N과 M (4)

• 원소가 주어지는 경우
  • N과 M (5 ~ 8)
  • N과 M (1 ~ 4)에서 원소에 대한 처리만 추가하면 된다.

• 중복 원소가 존재하는 경우
  • 15663 N과 M (9)
  • N과 M (10 ~ 12)는 (9)와 같이 set을 활용하며 로직은 N과 M 2 - 4와 동일하다.

 

문제

15652번: N과 M (4)

 

문제 풀이

 앞서 푼 문제 중 15650 N과 M (2)는 중복을 허용하지 않는 조합을 구하는 문제였다. 하지만 이 문제는 N개의 원소를 M개 선택할 때 중복을 허용하는 조합을 구하는 문제이다. 중복을 허용하지 않는 조합에 대한 로직을 이해하였다면 이 문제는 쉽게 풀 수 있다. 기존 조합을 구할 때는 재귀 호출을 할 때, 현재 선택된 원소를 선택하지 않도록 인덱스에 +1 씩 증가시켜주었다. 하지만 동일한 인덱스를 호출 할 수 있도록 하면 중복 조합을 구할 수 있다.

 

코드

DFS를 사용한 문제 풀이

from sys import stdin


# 순열과 달리 현재 인덱스의 값이 필요함.
def dfs(idx, depth):
    global answer
    # 재귀 종료 조건 → 선택하고자 하는 수
    if depth == m:
        answer.append([*check])
    else:
        for i in range(idx, n):
            check[depth] = i + 1
            dfs(i, depth + 1)

if __name__ == '__main__':
    answer = []
    n, m = map(int, stdin.readline().split())
    check = [0] * m
    dfs(0, 0)

    for num in answer:
        print(*num)

 

itertools combinations_with_replacement를 활용한 문제 풀이

from itertools import combinations_with_replacement

N, M = map(int, input().split())
nums = [num + 1 for num in range(N)]
for cases in combinations_with_replacement(nums, M):
    for case in cases:
        print(case, end=' ')
    print()