https://www.acmicpc.net/problem/15652
15652번: N과 M (4)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
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의 개수까지 될때까지 현재 값보다 큰 값을 넣어주기만 하면 된다.
그럼 우리는 처음 값만 잘 넣어주고 반복되는 과정만 적어주면 된다.
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준] 14940번 : 쉬운 최단거리 (python 파이썬) (0) | 2024.04.20 |
---|---|
[백준] 2630번 : 색종이 만들기 (python 파이썬) (0) | 2024.04.18 |
[백준] 1002번 : 터렛 (python 파이썬) (0) | 2024.04.18 |
[백준] 1932번 : 정수 삼각형 (python 파이썬) (0) | 2023.01.24 |
[백준] 2606번 :바이러스 (python 파이썬) (0) | 2022.12.31 |