[백준] 15650 N과 M(2) 파이썬

2020/03/02 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15649. N과 M (1) 파이썬

 

문제집 출처 :: 백준 N과 M https://www.acmicpc.net/workbook/view/2052

---

* DFS 재귀방식을 이용한 파이썬 풀이입니다.

문제출처 https://www.acmicpc.net/problem/15650

[백준] 15650 N과 M(2) 파이썬

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

<PASS>

# 2번. [백준] 15650
# 1~n 중에 m 개 뽑기. 중복 안되게. 순서없음. [1,2]=[2,1]같은 것으로 봄
n,m = map(int,input().split())
numbers = [i+1 for i in range(n)] # 1~n까지
is_number = [0 for _ in range(m)] # 출력 개수
check = [False for _ in range(n)] # 사용여부(씀=True, 안씀= False)
def dfs(idx,next):
    if idx >= m: # 0부터 m출력개수 되면 리턴!
        print(*is_number)
        return
    for i in range(next,n):
        #숫자를 사용 안했다면
        if not check[i]:
            #나는 i 번째 숫자를 사용하겠어
            check[i] = True
            #숫자를 배치하겠어
            is_number[idx] = numbers[i]
            # 다음은 알아서 재귀해~
            dfs(idx+1,i+1) # next 에 i+1 이란 것을 다음 재귀next로 알아먹음
            #사용다했어
            check[i] = False
            
dfs(0,0)
 

 

---

<시행착오>

함수 내에서 재귀를 할 때, 다음에 변화하는 값 인수 명을 잘 써주자..

 

# for i in range(next,n) 
다음 포문 돌 영역은 지금 True 로 사용된 i 보다는 커야 한다고 생각해
 
재귀로 한단계 들어갈 때, next 로 i+1을 해야 하는데,
인자 그 자리에 next란 이름이 꼭 들어가야 한다고 착각함. 
next+i 로 깊이 생각하지 않고 사용...띠로리..

n,m = X,2 도 원하는 값이 나오는데

n,m = 5,3 부터 출력값이 뭔가 모자라게 나오기 시작해서 고민..한시간...ㅋㅋㅋㅋ

 

디버깅 잘 할 줄 모르는 또르르.. 

next 값이 변화가 하나씩 안되고 껑충껑충 된다는 걸 알고 고침! 성공!

재귀를 들어갈 때, 어떤게 어떻게 영향을 줄지 애초에 생각을 잘해보쟈