[백준알고리즘] 15651번: N과 M (3) -Python

[백준알고리즘] 15651번: N과 M (3) -Python

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

15651번: N과 M (3)

N과 M (1)과 N과 M(2)를 풀면서 느낀건데 백트래킹을 적용하고 있다고 생각이 들지 않았다.

 

여기서 BackTracking을 적용하기 위해서는 DFS처럼 가능한 경우들을 트리로 형성을 한 후에 Prunning을 통해 최선의 경로가 아닌 경우는 방문하지 않는 방법을 적용해야 한다.

하지만 위의 문제들에서는 딱히 그런 게 없던 것 같기 때문에 우선은 쭉쭉 풀고 N과 M을 벗어나야겠다.

 

이번에는 다른 방법으로 풀 수도 있지만 그냥 N과 M (1)에서 보였던 itertools의 product를 통해 조합을 출력하도록 했다. 얼른 넘어가도록 하자!

 

import sys
from itertools import product

def testCase():
    input_val = list(map(int, sys.stdin.readline().split()))
    global N, M
    N, M = input_val

def solve(remain):
    res = list(map(' '.join, product(remain, repeat=M)))
    print('\n'.join(res))

if __name__ == "__main__":
    testCase()
    solve(map(str, list(range(1, N+1))))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다