백준: 15651 N과 M (3)

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와 동일하다.

 

문제

15651번: N과 M (3)

 

문제 풀이

 앞서 풀이 한 15649 N과 M (1)를 이해하였다면 이 문제는 더 쉽게 풀 수 있다. 중복을 허용하는 순열을 구하는 문제이므로 중복을 체크하는 구문을 삭제 해주면 N개의 수에 대한 M 길이의 중복 순열을 구할 수 있다

 

코드

DFS 사용한 문제 풀이

from sys import stdin


def dfs(depth):
    global answer
    # 재귀 종료 조건 → 선택하고자 하는 수
    if depth == m:
        answer.append([*check])
    else:
        for i in range(n):
            # 별도의 중복 확인이 필요 없음
            check[depth] = i + 1
            dfs(depth + 1)

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

    for num in answer:
        print(*num)

 

itertools product를 활용한 문제 풀이

from itertools import product

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