[백준] 15652 N과 M (4) (실버3) / 백트래킹

문제요약

나의 코드 및 설명 

• ans에 수열을 직접 집어넣고 출력한다.
• for문을 돌릴 때 ans의 마지막에 저장된 수(바로 이전 함수에서 저장된 수)보다 i가 작을 경우엔 넘어가고, 그렇지 않을 경우엔 비내림차순에 해당되므로 i를 추가하고 다음 함수를 호출한다.

def dfs(index):
    if index == m:
        print(" ".join(map(str, ans)))
        return
    for i in range(1, n+1):
        if len(ans) != 0:
            if ans[-1] > i:
                continue
        ans.append(i)
        dfs(index+1)
        ans.pop()

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

dfs(0)

다른 코드 및 설명

• 함수의 두 번째 변수로 temp(수열의 시작값)을 주었다.
• 함수를 호출할 때 변수로 수열의 시작값을 줌으로써 for문을 돌릴 때, 자연히 현재의 수보다 같거나 큰 수를 다음 함수의 변수로 준다.

def dfs(index, temp):
    if index == m:
        print(" ".join(map(str, ans)))
        return
    for i in range(temp, n+1):
        ans.append(i)
        dfs(index+1, i)
        ans.pop()

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

dfs(0,1)

피드백

이전 문제에서 조금 숙달된 것처럼 보였는데, 아직도 흐름을 몰라서 갈팡질팡이다.. ㅠ 여러 문제를 풀어보다보면 조금 나아질 것을 기대하며 ... 다음 문제도 화이팅!