[BOJ][Python] [15651] N과 M(3)

[문제 및 출처]

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

[어떻게 풀까?]

사실 이 문제는 N과 M(1)문제를 풀다가 실수로 풀어버렸다.

문제의 조건은 다음과 같다. 이 문제는 중복을 허용하는 문제이다.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

코드는 다음과 같다.

[코드]

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

used = [False] * (N+1)
answer = []

def dfs(N, M):
    #조건에 충족하면 출력
    if len(answer) == M: 
        print(" ".join(map(str, answer)))
        return

    for i in range(1 , N+1):
        if not used[i]: 
            #이 부분을 지워준다. used[i] = True
            answer.append(i)

            dfs(N, M)
            
            #다시초기화
            #이 부분도 같이. used[i] = False 
            answer.pop()

dfs(N, M)

[코드설명]

1번 문제와 비교해서 딱 2줄만 없애주면 된다. 아! 지금보니까 애초에 used를 사용할 필요가 없지 않을까??

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

#used = [False] * (N+1)
answer = []

def dfs(N, M):
    #조건에 충족하면 출력
    if len(answer) == M: 
        print(" ".join(map(str, answer)))
        return

    for i in range(1 , N+1):
        #if not used[i]: 
            #이 부분을 지워준다. used[i] = True
            answer.append(i)

            dfs(N, M)
            
            #다시초기화
            #이 부분도 같이. used[i] = False 
            answer.pop()

dfs(N, M)

이런식으로 말이다. 애초에 used의 목적이 중복을 체크하기 위함이었는데 중복을 허용해 버렸으니,

이제 used는 필요없는 함수가 된 것이다. 단순히 재귀함수로 만들어 출력을 해주면 된다. 간단하디 간단한 문제였다.