[백준 15650] N과 M (2) - python (solved.ac - 실버 3)

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

15650번: N과 M (2)

풀이

문제를 보았을때 알수있는 힌트

문제를 보고 간단하게 푸는 방법으로는 조합을 출력되게하면 끝이 나겠구나? 생각이 들었다.

파이썬에는 itertools의 combinations 가 존재하기에 이것을 이용하면 엄청 쉽게 풀 수 있다.

 

import sys
from itertools import combinations

input= sys.stdin.readline

n,m = map(int,input().split())

n_list = [i for i in range(1,n+1)]
result =list(combinations(n_list,m))
for i in result:
    print(*i)

 

하지만 문제의 의도는 백트래킹을 할 줄 아는 사람이 되어라는 문제이다.

그렇다면 dfs를 이용하여 백트래킹을 통해 문제를 풀어보자.

백트래킹은 dfs에 들어갔을때와 나왔을때는 다시 뒤로 돌려주는 것을 의미 한다.

이를 생각하면서 문제를 풀면 될 것이다.

import sys

input= sys.stdin.readline
def dfs(x,y):
    if m==y:
        print(*x)
    else:
        for i in range(x[-1]+1,n+1):
            x.append(i)
            dfs(x,y+1)
            x.pop()

n,m = map(int,input().split())


for i in range(1,n+1):
    temp=[i]
    dfs(temp,1)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon15650.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리