백준 15652번 - N과 M (4) - 파이썬(Python)

백준 1018번 - 체스판 다시 칠하기 - 파이썬(Python)

문제 링크

https://www.acmicpc.net/problem/15652

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
• 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력 조건

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

출력 조건

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

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

입력 예시1

3 1

출력 예시1

1
2
3

 

입력 예시2

4 2

출력 예시2

1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

입력 예시3

3 3

출력 예시3

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

 

풀이 전 생각

 우선, 문제의 베이스 조건(재귀의 종료조건)을 생각했다. 한번 print 할 때 입력받은 m만큼 수열을 출력하게 되므로 m == len(l) (l은 입력받을 list) 가 베이스 조건이 될 것이다. 그렇게 작성한 후 코드를 실행해보고 약간의 수정을 하면 될 것 같다. 

 

예제 코드(완성 전)

n,m = map(int,input().split())

l = []
def function():
    if m == len(l):
        print(' '.join(map(str,l)))
        return
    for i in range(1,n+1):
        l.append(i)
        function()
        l.pop()
function()

 

그리고 나온 출력 결과는 다음과 같다

3 3
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

1 1 3이 출력된 이후에 1 2 2 가 출력되어야 하는데, 1 2 1 이 출력되고 있는 것을 볼 수 있다.

문제의 조건(비내림차순)을 만족하기 위해서는 funtion 함수가 재귀로 불릴 때 반복문에서 i를 인자로 보내주어야 할 것 같다. 

그래서 최종 코드는 다음과 같다.

 

예제 코드(완성 후)

n,m = map(int,input().split())

l = []
def function(start):
    if m == len(l):
        print(' '.join(map(str,l)))
        return
    for i in range(start,n+1):
        l.append(i)
        function(i)
        l.pop()
function(1)

생각

 재귀함수를 이해하기 위해서 팩토리얼이나 피보나치 등의 문제로 함수가 호출되고, 실행되는 순서에 대해서 하나하나 따라가며 공부를 했다. 재귀의 개념은 어느정도 이해가 되지만 호출하는 횟수가 많아지고 복잡해지게 되면 함수의 실행 순서를 따라가는 것이 정말 버겁고, 코드를 봐도 이해가 안가는 문제들도 많은데 다들 어떻게 해결하는 걸까? 하는 생각이 들었다.   

 이게 정답일지는 모르겠지만 아래 참고자료의 블로그에서 좋은 인사이트를 얻었다. 

내가 매번 하던 것처럼 재귀적으로 함수의 실행순서를 일일히 따라가는 것이 아니라 오히려 재귀적으로 생각하지 않는 것이다.

이번 문제를 풀 때도, 1차적으로 베이스 조건만을 생각하고 문제를 푸니 이전보다 많이 문제풀이가 편해진 느낌이었다.

이 인사이트를 이용해 재귀와 관련된 다른 문제들도 해결해보고, 어렵다면 또 다른 방법이 있을지 고민해보는 것도 좋을 것 같다. 

 

참고 자료

재귀 문제 풀이 인사이트

https://velog.io/@eddy_song/you-can-solve-recursion

야, 너두 재귀할 수 있어: 재귀가 풀리는 4단계 접근법

재귀함수 동작 시각화 사이트

https://pythontutor.com/render.html#mode=edit

Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java