#15650

15649 번 - N과 M(1)의 응용 버전이다.

고른 수열이 오름차순이여야 한다.

처음 짰던 코드 - 풀이 1

N, M = map(int, input().split())

numList = []

def dfs():
    if len(numList) == M:
        for i in range(0, M):
            if i == M-1:
                # 젤 마지막 전에꺼 비교할 때는 예외처리
                if numList[M-2] > numList[M-1]:
                    return
                else:
                    continue
            else:
                if numList[i] > numList[i+1]:
                    return
                else:
                    continue
        for i in range(0, M):
            print(numList[i],'',end='')
        print()

        return

    for i in range(1, N+1):
        if i not in numList:
            numList.append(i)
            dfs()
            numList.pop()
    
dfs()

똑같이 수열을 구하고, 이를 출력할 때 다시 배열을 돌면서 앞의 숫자가 뒤에 숫자보다 값이 크다면? return을 해줘서 출력을 안하게 했다.

이렇게 해서 정답이 나왔지만, 정현이 형이 조언을 해줬다.

이 문제에서는 이렇게 풀 수 있겠지만, 오름차순으로 다른 문제가 나오면 안될 수도 있다고 했다.

수열을 이전과 그대로 똑같이 구해주고 출력에서만 조건을 걸어주었는데 처음엔 index 에러가 떠서 (당연히 나올 수 밖에..) if i == M-1: 조건을 추가해주고.. 어찌 저찌해서 풀었다.

하지만 답답하게 지켜보던 조정현 등판.

풀이 2

N, M = map(int, input().split())

numList = []

def dfs(idx):
    if len(numList) == M:
        for a in numList:
            print(a,'', end='')
        print()
        return

    for i in range(idx, N+1):
    	if i not in numList:
        	numList.append(i)
        	dfs(i+1)
        	numList.pop()
       
dfs(1)

이 풀이의 핵심은 바로

오름차순이잖아? 인덱스로 출발점을 넘겨주면 돼. 그럼 당연히 뒤에 애들은 그거보단 크겠지.

정말.. 아직까지도 이 때의 그 짜릿함을 잊을 수가 없다. 어떻게 이런 생각을 할 수 있을까

출력에서 이러쿵 저러쿵 하지 말고 애초에 수열을 만들 때부터 오름차순으로 만들어줘버리면 된다. dfs를 돌기 전에 출발점을 넘겨주어 그 바로 다음부터 for문을 돌게 하는 것이다 (이전의 코드에서는 무조건 1부터 다시 시작, if 문으로 이미 있는거 걸러내기)

지금 생각해보면 진짜 너무 당연하다. 진짜 대단하다. 문제 많이 풀어보자. 나도 할 수 있다.

하지만 위의 코드도 아직 완성은 아니다. 고칠 수 있는 부분이 있다.

바로 << if i not in numList: >> 이 부분 !!

출발점을 dfs를 호출했던 숫자보다 하나 크게 했으니 당연하게 너무나 당연하게 i는 numList에 없을 것이다. 따라서 저 구문은 무조건 항상 True 이다. 따라서 굳이 없어도 된다.

최종 코드

N, M = map(int, input().split())
numList = []

def dfs(idx):
    if len(numList) == M:
        for a in numList:
            print(a,'', end='')
        print()
        return

    for i in range(idx, N+1):
        numList.append(i)
        dfs(i+1)
        numList.pop()

dfs(1)

if 문 하나 빼줬다고 시간이 2배나 줄었다. (152 -> 68)