백준 : N과 M (4)

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

15652번: N과 M (4)

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

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

 

비슷한 순열 문제이다. 결과 수열이 '비내림차순' 이라는 조건이 더해졌다.

 

n, m = map(int, input().split())
l = [(i+1) for i in range(n)]
result = [0]*m

def over_perm(l, n, m, level):
    if level == m:
        if result == sorted(result):
            print(' '.join(str(i) for i in result))
        return
    for i in range(n):
        result[level] = l[i]
        over_perm(l,n,m,level+1)

over_perm(l,n,m,0)

 

이런 식으로 결과값을 내보내는 곳에 if 문 만 넣었더니 시간초과가 나왔다.

결과를 하나하나 확인하면 안되고 처음부터 싹을 자르는 방법이 더 빠르다!

 

n, m = map(int, input().split())
l = [(i+1) for i in range(n)]
result = [0]*m

def over_perm(l, n, m, level):
    if level == m:
        print(' '.join(str(i) for i in result))
        return
    for i in range(n):
        if level > 0:
            if l[i] >= result[level-1]:
                result[level] = l[i]
                over_perm(l, n, m, level + 1)
        else:
            result[level] = l[i]
            over_perm(l,n,m,level+1)

over_perm(l,n,m,0)