[백트래킹, 백준] N과 M (1), (2) <중복을 허용하지 않는 순열, 조합>

N과 M - 1, 2의 차이

1번에서는 중복을 허용하지 않는 순열, 2번에서는 조합을 뽑는 문제이다.

 

1번에서는 단순히, 중복에 대해 체크하는 1차원 리스트를 만들어 플래그로 활용하면서, 재귀적으로 호출하면 쉽게 해결할 수 있다.

 

n, m = map(int, input().split())
arr = [i + 1 for i in range(n)]
selected = [False] * n
result = []


def permutation(m):
    if m == 0 :
        print(*result)
        return

    for idx in range(n):
        if not selected[idx] :
            selected[idx] = True
            result.append(arr[idx])
            permutation(m - 1)
            result.pop()
            selected[idx] = False


permutation(m)

2번에서는, 이렇게 단순하지 않다.

핵심은, 재귀적으로 사용되는 인덱스/카운터와 반복문의 시작점을 따로 관리해줘야 하는 것이다.

 

예시로

 

1 | 2 3 4

2 | 3 4

3 | 4

 

라고 되있으면, 바로 시작하는 수(첫번째 수)와 다음수(두번째 반복문에 관련, 인덱스로 컨트롤 예정)간

1의 차이가 나는 규칙성이 보이는 것을 알 수 있다.

 

이를 토대로 코드를 변경 구현을 해보면, 아래와 같다.

 

n, m = map(int, input().split())
arr = [i + 1 for i in range(n)]
result = []

def combination(cnt, start):
    if cnt == m :
        print(*result)
        return

    for idx in range(start, n):
        result.append(arr[idx])
        combination(cnt + 1, idx + 1)
        result.pop()

combination(0, 0)

 

 

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

15649번: N과 M (1)

 

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

15650번: N과 M (2)