[실버 III] 15650번. N과 M (2)

 문제 

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

15650번: N과 M (2)

 사용 언어 

Python3

 풀이 과정 

이 문제는 조합(combinatoin)을 이용하는 법 / 백트래킹(DFS)을 이용하는 법 이렇게 두 가지 버전으로 풀었다.

조합은 진짜 쉽게 풀었지만, 백트래킹을 구현하는 과정에 있어서 N과 M (2)에 추가된 조건인 오름차순 수열만 출력하는 방식이 추가되었는데...

 

나는 처음에 for문을 수정하지 못하겠어서 출력시에 오름차순 정렬인지를 확인해 맞는 경우만 출력하도록 했고 이 방식이 굉장히 마음에 안들었다. 시간이 오래 걸릴 걸 예상했는데 역시나 combination 방식보다 훨씬 오래 걸렸다.

# 백트래킹 ver 1
def backtracking(idx):
    if idx == M:
        if sorted(combi) == combi:
            print(*combi)
        return

    for i in range(1, N + 1):
        if not isused[i]:
            combi[idx] = i
            isused[i] = True
            backtracking(idx + 1)
            isused[i] = False

답은 맞지만 이렇게 하면 결국엔 필요없는 for문도 다 돌면서 수열을 만드는 과정이 포함되기 때문에 백트래킹의 장점을 살리지 못하는 걸 알고 있었다..ㅎㅎ

 

그래서 (좀 오랜) 고민 끝에 수정해서 제출 답안에 있는 걸로 바꿨고 그 결과 조합을 사용한 방법보다 확실히 빨랐다!! 백트래킹 좋은 거였따..

 

어쨌든 깔끔하게 세 번 맞았습니다!!

(아래 조합 ver / 중간 백트래킹 ver 1 / 맨 위 백트래킹 ver 2)

 

 제출 답안 

# 조합
from itertools import combinations
from sys import stdin
input = stdin.readline

N, M = map(int, input().split())
N_list = [x for x in range(1, N + 1)]
combi = list(combinations(N_list, M))
for i in range(len(combi)):
    print(*combi[i])

# 백트래킹 ver 2
from sys import stdin
input = stdin.readline

N, M = map(int, input().split())
N_list = [x for x in range(1, N + 1)]

combi = [0] * M
isused = [False] * (N + 1)

def backtracking(num, idx):
    if idx == M:
        print(*combi)
        return

    for i in range(num, N + 1):
        if not isused[i]:
            combi[idx] = i
            isused[i] = True
            backtracking(i + 1, idx + 1)
            isused[i] = False

if __name__ == "__main__":
    backtracking(1, 0)