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

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

15651번: N과 M (3)

 

---

• 문제
• 소요시간: 3분 6초

---

• 설계하기(접근방법) 

1. 입력받기

n, m 을 입력받는다

 

2. 구현하기

백트래킹의 변형이지만 실제로는 재귀함수 문제같다

visited를 코드에는 선언했지만 필요없었다

 

1 ~ n까지 차례때로 선택하고, 중복을 허락한다

즉 visited를 검사할 필요가 없다

 

 

3. 출력하기

ans를 출력한다

 

---

• 코드(출력)

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

ans = []
visited = [0 for _ in range(n + 1)]

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

dfs(0, [])

for i in ans:
    print(*i)

---

• 얻어갈 부분

1. 요구 사항, 종료조건에 맞게 코드를 구현하자