61. 백준 : N과 M(2)

 

백트래킹같다.

 

하나 넣고 돌리고, 그거 빼는 식

 

기본적으로 하나 빼고 다음 거 넣고 이런 식이라고 생각하면 된다.

1 2 3

1 2 4

> 1,2 로 해서 들어갈 수 있는 거 다 들어가기

   끝나면 1 만 해서 들어갈 수 있는 거 돈다

 

1 3 4

> 1로 시작하는 건 이게 다인 듯

 

2로 시작하는 걸로 보면

2 3 4

> 끝

def backtracking(i):
    if len(res) == M:
        print("----",*res)
        return
    
    for i in range(i,N+1):
        if i not in res:
            print(i,"넣을 예정")
            res.append(i)
            backtracking(i+1)
            print(i,"뻅니다")

            res.pop()

N,M = map(int,input().split())
res = []

backtracking(1)

 

BackTracking 구조는 다음과 같은 것 같다.

 

현재 단계 연산 대상 추가

➡️ 연산

➡️ 현재 단계 빼고 다음 단계 넣기

 

---

생각해보니 백트래킹 문제를 많이 안 푼 것 같다.

이번 기회에 좀 많이 풀어두자.