[백준] 15650 파이썬(python) : N과 M (2) - (combinations이용)

15650번 : N과 M (2)

 

 

 

n, m = map(int, input().split())
answer = []
def backTracking(index):
    if len(answer) == m: #1
        print(" ".join(map(str, answer)))
        return
    
    for i in range(index, n+1): #2
        if i not in answer:
            answer.append(i)
            backTracking(i+1) #3
            answer.pop()
backTracking(1) #4

 

15649번과 비슷한 문제다.

#1 : stack의 길이가 입력값 m과 같아지면 스택의 원소들을 출력한다.

#2, 3 : 현재 원소 스택에 있는 숫자보다 작은 숫자는 스택에 넣으면 안되기 때문에 반복문의 시작을 index로 하고 그 다음으로 넘겨주기 위해서 i+1을 다음 재귀함수의 인덱스로 한다.

#4 : 스택에 들어가는 첫번째 원소의 예시가 1이므로 인자로 1을 넣는다.

 

다른풀이)

import sys
n, m = map(int, sys.stdin.readline().split())
res = []
def backTracking(depth):
    if len(res) == m:
        print(*res)
        return
    for i in range(depth, n+1):
        if len(res) == 0 or res[-1] < i:
            res.append(i)
            backTracking(depth+1)
            res.pop()
backTracking(1)

res리스트에 삽입하는 조건을 조금 다르게 해봤습니다.

 

다른풀이)

import sys
n, m = map(int, sys.stdin.readline().split())
res = []
def backTracking(depth):
    if depth == m:
        print(*res)
        return
    for i in range(1, n+1):
        if len(res) == 0 or res[-1] < i:
            res.append(i)
            backTracking(depth+1)
            res.pop()
backTracking(0)

 

조합을 이용한 풀이)

조합을 이용해서 풀 수도 있다.

import sys
from itertools import combinations
n, m = map(int, sys.stdin.readline().split())
numbers = list(range(1, n+1)) #1
for i in combinations(numbers, m): #2
    print(*i) #3

 

#1 : 1부터 n까지의 숫자를 포함하는 리스트 생성

#2 : combinations를 활용해서 arr중 m개를 뽑아 순서를 고려하지 않고 뽑습니다.

#3 : 아스테리스크를 이용해서 리스트를 풀어주며 출력해줍니다.

 

아래가 백트래킹 위는 조합으로 풀이