[solved.ac 실버3] 15651_N과 M (3) (python, brute force)

제약 사항

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

---

나의 풀이

n과 m은 7까지 입력될 수 있다.

즉, 1111111 ~ 7777777 까지 출력되는 경우가 가장 큰 경우이며, 7^7 = 823,543 개의 경우의 수가 나오기 때문에 컴퓨터가 1초에 대략 1억번 반복할 수 있다고 한다면 1초 내에 충분히 가능한 경우의 수인 것이다.

이처럼 모든 경우의 수를 확인하는 경우는 전체 탐색(Brute Force)으로 풀 수 있다. 여기서는 재귀 함수로 풀이했다.

 

4와 3이 입력되었을 때

사람의 경우라면

111, 112, ..., 114 가 입력되면 1의 자리에서 더 이상 올릴 수 없으니 121 로 올라가게 된다. 같은 방식으로 144까지 도달하면 10의 자리에서 더 이상 올릴 수 없으니 211로 올라가고, 같은 방식으로 계속 진행하면 444까지 올라가게 된다.

 

사람의 방식과 비슷하게 코딩하면 된다.

n, m = map(int, input().split())
selected = [0] * (m+1)

우선 n과 m을 입력 받고, selected라는 리스트를 m+1의 크기로 (0으로) 초기화한다.

만약 4와 3이 입력되었다면 4칸짜리 selected 리스트를 선언하는 것이다.

이때 m+1이 아닌 m 크기로 해도 상관 없으나 리스트는 0번째 인덱스부터 시작하기 때문에 크기를 1 크게 만들어서 0번째 인덱스를 사용하지 않고, 1번째 인덱스를 시작 인덱스처럼 사용할 것이다.

 

def rec_fun(k):
    if (k == m+1):
        for i in selected[1:]: print(i, end=' ')
        print()
    else:
        for cand in range(1, n+1):
            selected[k] = cand
            rec_fun(k+1)
            selected[k] = 0

k는 selected에서 몇 번째 칸인지를 뜻한다. 즉, if문의 k == m+1 이라는 조건은 selected의 마지막 인덱스(selected가 m+1 크기이다) -> 1의 자리를 가리키는지를 뜻한다.

k가 1의 자리를 가리킨다면 현재 selected에 저장된 숫자를 출력한다. (selected가 완성된 경우에 출력을 한다는 의미이다)

 

이제 else문을 살펴보자.

for문의 cand는 1~n까지 반복하며 selected에 저장될 숫자를 의미한다.

k번째 자리에 cand의 값을 저장한 후 rec_fun을 한 번 더 부르는 재귀 호출을 수행한다.

즉, 첫 번째 자리, 두 번째 자리 ... m+1번째 자리까지 쭉 숫자를 채우겠다는 뜻이다. (그리고 m+1까지 도달하면 출력한다)

출력 후 빠져 나오면 selected[k] = 0 을 수행하는데 이는 사실 없어도 되는 부분이지만 관례상 0으로 다시 초기화 해주는 작업이다.

n, m = map(int, input().split())
selected = [0] * (m+1)
def rec_fun(k):
    if (k == m+1):
        for i in selected[1:]: print(i, end=' ')
        print()
    else:
        for cand in range(1, n+1):
            selected[k] = cand
            rec_fun(k+1)
            selected[k] = 0

def solution():
    rec_fun(1)
    
solution()

k를 1부터 시작하는 rec_fun(1)을 호출하게 되면 풀이 완료이다.

 

채점 결과