[백준] 15650번 : N과 M (2) (🥈실버 2) (Python)

문제 바로 가기

15650번: N과 M (2)

 

---

풀이

• 사용 언어 : Python
• 풀이한 날짜 : 2022-02-10

 

n, m = tuple(map(int, input().split()))
lst = []


def print_lst():
    for elem in lst:
        print(elem, end=" ")
    print()

def choose(curr_num):
    if curr_num == m + 1:
        print_lst()

    for i in range(1, n + 1):
        if len(lst) >= 1 and lst[-1] >= i:
            continue

        lst.append(i)
        choose(curr_num + 1)
        lst.pop()


choose(1)

 

풀이 로직

• 재귀 함수를 이용하는 Backtracking 방법으로 문제를 해결하였다.
• 우선 숫자를 한 개 뽑고 이를 리스트에 삽입한 후 같은 함수를 m개의 숫자를 뽑을 때까지 반복 호출한다.
  • 재귀 함수 호출 이후엔 pop 메소드를 통해 리스트를 원래대로 복귀시켜 놓아야 한다.
• 오름차순으로 수를 뽑아야 하므로, 바로 이전에 뽑았던 수보다 같거나 작은 수를 뽑는 과정은 continue문을 통해 생략한다.

 

문제 접근 과정 및 느낀점

• Backtracking 유형의 대표 문제
• 재밌다.