백준 15650번 N과 M (2)

백준 15650번 N과 M (2) 이다.

이전 N과 M (1)과 문제가 비슷하다. 이번에는 오름차순이어야 한다는 조건이 추가되었다.

이번에도 역시 백트래킹 문제이다.

이번에는 한 숫자를 골랐다면 다음자리에는 그보다 작은 숫자가 올 수 없기 때문에

check 배열에서 고른 숫자 이하의 자리는 모두 +1 해주고 빠져나오면 -1을 해 주었다.

물론 고를때에는 1이 아닌것으로가 아닌 0인지로 판단해주었다.

언어는 python을 사용하였다. 

def func(cnt):
    if cnt == m:
        for i in range(m):
            print(list1[list2[i]], end = ' ')
        print()
    for i in range(n):
        if check[i] == 0:
            
            for j in range(i+1):
                check[j] += 1
            list2[cnt] = i
            func(cnt+1)
            for j in range(i+1):
                check[j] -= 1


n, m = input().split()
n = int(n)
m = int(m)
list1 = [1,2,3,4,5,6,7,8]
list2 = [0,0,0,0,0,0,0,0]
check = [0,0,0,0,0,0,0,0]
func(0)

이전과 거의 유사하지만 오름차순에 대한 처리만 해주면 되는 문제였다. 

성공!