15650번: N과M(2)

15650번: N과 M (2)

15649번 N과M(1) 문제와 거의 똑같지만 다른 점은, 

고른 수열이 오름차순이어야 한다는 점!

 

---

# 15650번: N과M(2)

n, m = map(int, input().split())

visited = [False] * (n+1)
result = [0]

temp = 0

def backTracking(num):
    if num == m:
        print(*result[1:])
        return
    
    for i in range(1, n+1):
        if not visited[i] and i > max(result):
            visited[i] = True
            result.append(i)
            backTracking(num+1)
            visited[i] = False
            result.pop()


backTracking(0)

backTracking 함수를 돌면서 수열에 들어갈 숫자를 고를 때, 해당 숫자(i)가 지금까지 들어간 수열의 최댓값보다 큰 경우에만 숫자를 넣도록 한다.

result 배열을 0으로 초기화해줬으므로, 0은 빼고 출력해야 한다.

그러므로 result[1:]을 출력한다.

 

---

다른 풀이

# 15650번: N과M(2)

n, m = map(int, input().split())

visited = [False] * (n+1)
result = []

temp = 0

def backTracking(num):
    if len(result) == m:
        print(*result)
        return
    
    for i in range(num, n+1):
        if not visited[i]:
            visited[i] = True
            result.append(i)
            backTracking(i+1)
            visited[i] = False
            result.pop()


backTracking(1)

굳이 최댓값을 비교하는게 아니라, backTracking 재귀를 돌 때, 수열에 들어갈 숫자 + 1을 재귀로 돌면, 최댓값을 비교할 필요 없이 오름차순으로 수열을 만들 수 있다.

그리고 종료 조건은 N과M(1) 문제와 다르게, 출력할 수열의 길이가 m이 되는 경우에 result를 출력하고 종료한다.

 

---

참고

[Python/파이썬] 백준 알고리즘 15649번 - N과 M (1) (BackTracking)