[Python] 백준 풀기 15652 - N과 M (4)

파이썬 백준 15652번

실버3

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

15652번: N과 M (4)

 

 

 

문제 보기

 

 

 

 

문제 풀기

이전 문제 15651번에서 가능한 모든 숫자로 이루어진 수열을 찾는 코드에 조건을 추가.

 

수열에 새로이 추가되는 원소는 이전 원소보다 같거나 큰 수가 들어가야 하기때문에

i 로 for 반복문을 돌리면서 불러오는 재귀함수 fnDFS() 의 num_sequence 축적 원소들은 i 보다 작아질 수 없음.

즉, i 는 num_sequence 에 들어있는 최댓값 보다 작은 경우는 생각하지 않아도 됨.

ex) for 문에서 두번째 원소 i = 1 이 주어진, [2, 1, X] 의 경우 max(num_sequence) 는 2 이기에 if 문 작동 안 함. fnDFS() 작동 안 함.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

N, M = map(int, inputdata().split())

num_sequence = []

def fnDFS():
    if len(num_sequence) == M:
        print(*num_sequence)
        return
    
    for i in range(1, N + 1):
        num_sequence.append(i)
        if i == max(num_sequence):
            fnDFS()
        num_sequence.pop()
        
fnDFS()



# 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