Baekjoon) 15650 N과 M(2) - Python, 백트래킹

💭 나의 접근 방법

---

문제는 조합 문제이다. 조합문제는 하나의 인수를 고른후에 백트래킹을 이용해 다음 인수를 append하여(함수 호출) 원하는 개수에 맞을 때(종료 조건) 조합을 만드는 방식이다.

조합 구현

이를 이용해 문제를 접근하였다.

 

N = 4,M = 2 를 예시로 들면 노란색 화살표가 for 문을 돌고 [1] 백트래킹, 재귀함수를 이용해서 다음 범위에 있는 값들 for 문을 다시 돌게 된다. [1,2] 여기서 종료조건 M = 2 를 맞추므로 백트래킹을 나오고 pop()이 실행되어 [1] 이 된다. 그리고 다음으로 3 이 리스트에 들어가 [1,3]으로 진행된다.

 

 

 

💡 결과

---

# 15650 N과 M 2 S3
N,M = map(int,input().split())
arr = [i for i in range(1,N+1)] #1~N 까지 값을 넣어줌
result = []
def backtrack(start,backList):
    if len(backList) == M:
        result.append(list(backList)) #리스토 새로 정의 안해주면 pop할때 같이 빠짐!
        return
    for i in range(start,len(arr)):
        backList.append(arr[i])
        backtrack(i+1,backList) # i는 back 트래킹 범위
        backList.pop()
backtrack(0,[]) # 0번 인덱스부터 start
for i in result:
    print(*i)

 

 

 

💫 느낀점

---

백트래킹 관련 문제들을 더 풀어보면서 백트래킹의 개념을 다시 정리해야할 것 같다. 

 

 

15650번: N과 M (2)