[백준/Python] 15650번 N과 M (2)

---

15650번: N과 M (2) (acmicpc.net)

---

코드

---

---

코드설명

---

본 문제는 '수열과 조합'에서 조합을 묻는 문제로 from itertools import combinations 을 활용해

1 ~ n 까지의 자연수 에서 m 길이 만큼의 조합을 출력하는 문제다.

하지만, 이는 '재귀함수'을 이용해서도 풀이가 가능하다.

 

go() 함수는 리스트 arr을 입력 받았을 때

len(arr) == m 일 시 리스트 arr를 출력하고, 

len(arr) != m 일 시 리스트 arr에 자연수 i을 추가하는 함수이다.

여기서 리스트 arr를 출력하고 '재귀적인 방법'을 사용했기에

함수 내 함수를 출력한 곳으로 return 한다.

 

for 문에서 재귀 함수를 이용해 풀이 시 조건문을 활용해

리스트 arr가 1) '비어 있을 때'  & 2) '비어 있지 않을 때'로 나눴다.

1) 경우 리스트에 항상 자연수 i을 추가한다.

2) 경우 자연수 i와 리스트의 max 값을 비교해 

max 값보다 큰 자연수 i만을 리스트에 추가한다.

---

이를 그림으로 표현하면 다음과 같다.

N = 2, M= 2일 떄를 예시로 들었다.