[백준 15650번] N과 M (2)

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

15650번: N과 M (2)

말그대로 조합을 구하라는 문제였다.

combinations 함수로 풀어도됐지만

조합 구현하는 방법을 아는건 중요하다 생각하기 때문에

직접 구현도 해보고 combinations 로도 풀어보았다.

 

혹시 몰라 c++로 조합과 순열 구현한 풀이도 한번 첨부해봄.. 

알고리즘 공부 할때 c++로 시작했기때문에 ㅎㅎ..

https://foameraserblue.tistory.com/62?category=481823 

조합과 순열 c++ 로 구현

 

직접 구현한 풀이

import sys
 
input = sys.stdin.readline
 
n, m = map(int, input().split())
# 1~n 까지의 자연수중에 m개를 선택하는 조합 문제
visit = [0 for i in range(n + 1)]
 
 
def print_num():
    for i in range(1, n + 1):
        if visit[i] == 1:
            print(i, end=' ')
    print('')
 
 
def dfs(x, cnt):
    if cnt == m:
        print_num()
        return
 
    for i in range(x, n + 1):
        if visit[i] == 1:
            continue
        visit[i] = 1
        dfs(i, cnt + 1)
        visit[i] = 0
 
 
dfs(1, 0)
 

 

combinations 함수를 사용한 풀이

 

import sys
from itertools import combinations
 
input = sys.stdin.readline
 
n, m = map(int, input().split())
# 1~n 까지의 자연수중에 m개를 선택하는 조합 문제
 
li = list(combinations(range(1, n + 1), m))
 
for l in li:
    print(' '.join(map(str, l)))