[백준] 15652번 : N과 M(4) (python 파이썬)
https://www.acmicpc.net/problem/15652
n, m = map(int,input().split(" "))
l = []
def dfs(start):
if len(l) == m:
print(' '.join(map(str,l)))
return
for i in range(start,n+1):
l.append(i)
dfs(i)
l.pop()
dfs(1)
위의 문제는 dfs로 풀 수 있다.
처음에는 for문의 계속 중첩해야 하나 싶었다....
시간을 계속 써봤지만 해결은 되지 않았고, 이런 for문도 못짜나 자괴감이 들었다....
하지만 애초에 for문의 중첩이 아니라 dfs 로 해결할 수 있었던 문제였다.
문제의 정답을 자세히 읽어보자.
1 1 1 1 1
1 2 1 1 2
1 3 1 1 3
1 4 1 2 2
2 2 1 2 3
2 3 1 3 3
2 4 2 2 2
3 3 2 2 3
3 4 2 3 3
4 4 3 3 3
아래를 보자
3 3일때 3 2일때 3 1일때
1 1 1
1 1 2
1 1 3 1 1
1 2 2 1 2 1
1 2 3
1 3 3 1 3
------------------------------------------
2 2 2 2 2
2 2 3
2
2 3 3 2 3
-------------------------------------------
3 3 3 3 3 3
뭔가 떠오르지 않는가..?
오른쪽에서 왼쪽으로 보면 규칙이 있는 거 같다.
시작 값이 1,2,3 인 경우에 따라
m의 개수까지 될때까지 현재 값보다 큰 값을 넣어주기만 하면 된다.
그럼 우리는 처음 값만 잘 넣어주고 반복되는 과정만 적어주면 된다.