[백준] 15652번 : N과 M(4) (python 파이썬)

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

15652번: N과 M (4)

 

 

 

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의 개수까지 될때까지 현재 값보다 큰 값을 넣어주기만 하면 된다.

 

 

그럼 우리는 처음 값만 잘 넣어주고 반복되는 과정만 적어주면 된다.