백준: 15650 N과 M (2)

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

 

문제

15650번: N과 M (2)

 

문제 풀이

 이전에 다룬 문제인 15649 N과 M (1)는 N개의 숫자 중에 M개의 길이의 순열을 구하는 문제였다. 이와 달리 N과 M (2)는 N개의 숫자 중에 M개의 조합을 구하는 문제이다. 순열은 (1, 2) (2, 1)을 모두 구하지만 조합은 이를 구하지 않는다.  즉 조합은 순서에 상관없이 원소가 같으면 같은 경우의 수로 생각한다. 이를 조합은 순서를 고려하지 않는다라고 표현하기도 한다. 15649 N과 M (1)에서 DFS를 통해 문제를 풀 수 있다는 것을 이해하였다면, 한 가지 조건만 추가하면 이 문제를 쉽게 풀 수 있다.

 

 

 그림과 같이 각 원소에 따라 선택할 수 있는 수는 위와 같다. 즉 1 이후에 다음 원소부터 선택할 수 있는 것은 자기 자신을 제외한 다음부터라는 것을 알 수 있다. 이를 위한 조건으로 DFS의 호출 조건에 현재 인덱스 값을 인자로 넘겨주면 쉽게 해결 할 수 있다.

 

코드

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 + 1, 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를 활용한 풀이

from itertools import combinations

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