[백준/BOJ] 백트래킹 N과 M시리즈(1)~(8)

백트래킹은 개념만 알고 있었고 코드 구현은 못했는데 이번에 N과 M 시리즈를 풀면서 좀 알게 됐다.

N과 M 시리즈(1)부터 (8)은 코드를 조금씩만 바꾸면 돼서 쭉쭉 풀었다.

근데 15663번부터 막혀서 이건 좀만 더 고민해봐야겠다.

 

15649번 N과 M(1)

import sys
input = sys.stdin.readline

def tracking(k):
    if(k == m):  # 종료 조건
        for i in range(m):
            print(arr[i], end=' ')
        print()
        return

    for i in range(1, n+1):
        if(checked[i] == False):
            arr[k] = i
            checked[i] = True
            tracking(k+1)
            checked[i] = False

n, m = map(int, input().split()) # n까지의 수, m:수열개수
checked = [False]*10
arr = [0 for _ in range(10)]
tracking(0)

 

15650번 N과 M(2)

import sys
input = sys.stdin.readline


def tracking(idx, k):
    if k == m:
        for i in range(m):
            print(arr[i], end=' ')
        print()
        return

    for i in range(idx, n+1):
        if checked[i] == False:
            checked[i] = True
            arr[k] = i
            idx = i
            tracking(idx, k+1)
            checked[i] = False

n, m = map(int, input().split())
checked = [False]*10
arr = [0 for _ in range(10)]

global idx
idx = 1
tracking(idx, 0)

=> 1번과 다른 점은 오름차순  정렬이다. 그래서 idx를 추가하여 idx 이후부터 백트래킹 돌면 된다.

 

15651번 N과 M(3)

import sys
input = sys.stdin.readline

def tracking(k):
    if k == m:  # 종료 조건
        for i in range(m):
            print(arr[i], end=' ')
        print()
        return

    for i in range(1, n+1):
        arr[k] = i
        tracking(k + 1)


n, m = map(int, input().split())
arr = [0 for i in range(8)]
tracking(0)

=> 1번과 다른 점은 중복을 포함한다는 점인데 그 숫자를 사용했는지 확인하는 checked 리스트 없이 진행하면 된다.

 

15652번 N과 M(4)

import sys
input = sys.stdin.readline

def tracking(idx, k):
    if k == m:
        for i in range(m):
            print(arr[i], end=' ')
        print()
        return

    for i in range(idx, n+1):
        arr[k] = i
        idx = i
        tracking(idx, k+1)


n, m = map(int, input().split())
arr = [0]*10
global idx
idx = 1
tracking(idx, 0)

=> 이 문제는 중복을 포함하면서 오름차순 정렬하면 된다.

 

15654번 N과 M(5)

import sys
input = sys.stdin.readline

def tracking(k):
    if(k == m):
        for i in range(m):
            print(answer[i], end=' ')
        print()
        return

    for i in range(1, n+1):
        if checked[i] == False:
            checked[i] = True
            answer[k] = arr[i-1]
            tracking(k+1)
            checked[i] = False


n, m = map(int, input().split())
checked = [False]*10
arr = list(map(int, input().split()))
arr = sorted(arr)
answer = [0]*10
tracking(0)

=> 이 문제는 1부터 n까지의 정수가 아니라 리스트를 입력해야 한다. answer list를 따로 만들어 주면 된다!!

 

15655번 N과 M(6)

import sys
input = sys.stdin.readline

def tracking(idx, k):
    if k == m:
        for i in range(m):
            print(answer[i], end=' ')
        print()
        return

    for i in range(idx, n+1):
        if checked[i] == False:
            checked[i] = True
            answer[k] = arr[i-1]
            idx = i
            tracking(idx, k+1)
            checked[i] = False

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr)
answer = [0] * 10
checked = [False]*10

global idx
idx = 1
tracking(idx, 0)

=> 5번과 다른 점은 이제 입력 받은 리스트를 오름차순으로 나열해주면 된다.

 

15656번 N과 M(7)

import sys
input = sys.stdin.readline

def tracking(k):
    if k == m:
        for i in range(m):
            print(answer[i], end=' ')
        print()
        return

    for i in range(1, n+1):
        answer[k] = arr[i-1]
        tracking(k+1)

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr)

answer = [0]*10
tracking(0)

=> 중복 포함해서 풀면 된다.

 

15657번 N과 M(8)

import sys
input = sys.stdin.readline

def tracking(idx, k):
    if k == m:
        for i in range(m):
            print(answer[i], end=' ')
        print()
        return

    for i in range(idx, n+1):
        idx = i
        answer[k] = arr[i-1]
        tracking(idx, k+1)


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr)
answer = [0]*10

global idx
idx = 1
tracking(idx, 0)

=> 오름차순으로 정렬하기 위해 idx를 추가해서 풀면 된다.

---