백준 15649. N과 M (1)

N과 M (1) ( https://www.acmicpc.net/problem/15649)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

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

예제 입력 1 

3 1

예제 출력 1 

1
2
3

---

[정답 코드]

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

def back(depth):

    if depth == M:
        print(*arr)
        return

    for i in range(1, N+1): # 1, 2, ... N으로 시작
        if i in arr:  # 중복 방지
            continue
        arr.append(i)
        back(depth + 1)
        arr.pop() # 전단계에서 다른 경우의 수를 찾기 위해 제거

f(0)

[정답 해설]

if문을 넣어 이미 arr 리스트에 있는 친구들은 건너뛰어 중복을 제거해주고,

arr 리스트에 1부터 N까지 차례로 넣고, depth를 1 늘려 재귀함수를 호출하고, 넣었던 친구를 빼고 다음 숫자(i)로 넘어간다.

[느낀점]

재귀도 결국 반복문 안의 반복문인 것임을...

i=1일 때 i=1, i=2, i=3....이렇게 들어가고

i=2일 때 i=1, i=2, i=3 ...이렇게 들어간다.

그리고 배열에 pop()을 해주는 것은 append로 하나 뽑은 후 재귀돌리고,

끝나면 다른 경우의 수를 찾기 위해 뽑은 걸 도로 빼주고 새로 시작하는 것이다.

def back(depth, lst):

    if depth == m:
        print(*lst)
        return

    for i in range(1, n+1):
        for i in lst:
            continue
        back(depth+1, lst + [i])
        lst.pop()

back(0, [])

여기서 이런 식으로 back 함수에 매개변수로 lst를 넣으면 어떻게 될까?

-> lst에 아무런 원소도 없는데 lst.pop()을 한다고 인덱스 에러가 난다.

lst + [i]로는 새로운 lst로 전달되므로 원래 있었던 lst(=[], 빈 리스트)는 그대로 있는 것이다.