[알고리즘/백트래킹] 15652번 : N과 M(4) - python

링크 : https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

 

---

• 문제
• 소요시간: 9분 26초

---

• 설계하기(접근방법) 

1. 입력받기

n, m 을 입력받는다

 

2. 구현하기

중복 순열을 전부 탐색한 후

중복을 제거해줄라고 했으나 시간 초과가 났다

그래서 백트래킹으로 풀었다.

 

dfs 내의 for문을 탐색할 때

이전에는 이전 숫자 + 1을 탐색했다면 1-> 2 -> 3

이번에는 이전 숫자부터 탐색하면 된다1 -> 1 -> 1

 

종료조건은 똑같이 m의 길이로 해주면

1,1,1

백

1,1,2

백

1,1,3....와 같이 탐색하게 된다

 

 

3. 출력하기

ans를 출력한다

 

 

---

• 코드(출력)

n, m = map(int, input().split())
ans = []

def dfs(cnt, lst, end):
    if cnt == m:
        ans.append(lst)
    else:
        for i in range(end, n + 1):
            dfs(cnt + 1, lst + [i], i)
            

dfs(0,[],1)

for i in ans:
    print(*i)

---

• 얻어갈 부분

1. 완전 탐색을 하면 시간초과가 난다는 것을 알게되었다. 백트래킹과 완전탐색의 시간복잡도는 다르기 때문에 이 부분을 고려해서 문제를 풀어주면 된다.