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

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

15663번: N과 M (9)

 

---

• 문제
• 소요시간: 25분 실패

---

• 설계하기(접근방법) 

1. 입력받기

n, m 과 수열을 입력받는다

 

2. 구현하기

num_list 내의 원소만 순회하면서 순열을 만든다

같은 숫자가 2개인 경우 2개를 사용 가능하나

같은 수열은 입력 못하는 것이 이 문제의 포인트이다

 

처음에는 리스트내에 새로 추가될 리스트가 없으면

append하는 방식으로 처리하려고 했으나

만약 8개 인 경우 순열의 개수가

8!  -> 5만 개가 되면서

시간초과를 하게 된다

 

dfs에서 빠져나올 때, 방금 탐색했던 원소를 변수로 저장하여

다음 for문의 탐색때 또 탐색하지 않도록 바꾸어야 한다

 

3. 출력하기

ans를 출력한다

 

 

 

 

---

• 코드(출력)

n , m = map(int, input().split())
num_list =list(map(int, input().split()))
num_list.sort()
visited = [0 for _ in range(n)]
ans = []

def dfs(cnt, lst):
    if cnt == m:
        if lst not in ans:
            ans.append(lst)
    else:
        before = 0
        for i in range(n):
                if visited[i] == 0 and num_list[i] != before:
                    visited[i] = 1
                    dfs(cnt + 1, lst + [num_list[i]])
                    visited[i] = 0
                    before = num_list[i]

dfs(0, [])

for i in ans:
    print(*i)

---

• 얻어갈 부분

1. 중복을 방지하기 위해 dfs에서 빠져나올 때 변수로 저장해놓는 것이 시간초과를 효과적으로 줄여주었다. 이 기법을 떠올리진 못했지만 기억해놓자