15652번: N과 M(4)

15652번: N과 M (4)

 

오늘도 돌아온 백트래킹 문제다.

이번에는 고른 수열이 비내림차순이어야 하고, 같은 수열을 여러번 골라도 된다.

 

 

---

# 15652번: N과 M(4)

n, m = map(int, input().split())
result = []


def backTracking(num):
    if num == m:
        print(*result)
        return
    
    for i in range(1, n+1):
        if len(result) == 0:
            result.append(i)
            backTracking(num + 1)
            result.pop()
        if len(result) > 0 and result[-1] <= i:
            result.append(i)
            backTracking(num+1)
            result.pop()


backTracking(0)

 

처음엔 이렇게 풀었다.

result가 비어있을 경우에는 그냥 i를 넣으면 된다.

그렇지만 result에 뭔가 들어 있을 경우에는 가장 마지막에 들어간 숫자와 i를 비교해서 i가 더 크거나 같은 경우에만 집어넣는다.

이렇게 하면 정답이긴 한데 더 깔끔한 다른 풀이가 있다.

 

---

풀이2

 

# 15652번: N과 M(4)

n, m = map(int, input().split())
result = []


def backTracking2(num):
    if len(result) == m:
        print(*result)
        return
    
    for i in range(num, n + 1):
        result.append(i)
        backTracking2(i)
        result.pop()

        

backTracking2(1)

 

종료조건은 result 리스트의 개수가 m개가 되었을 때로 정하고, 

num은 i로 넣는다.

그러면 항상 result에 추가되는 값은 바로 직전에 들어간 값 이상이므로 답이 나온다.

 

계속 풀어야 익숙해질듯?