[BOJ_Python] 15663 ~15666. N과 M 시리즈 3 (9 ~ 12)

문제

N과 M(9) : https://www.acmicpc.net/problem/15663

N과 M(10) : https://www.acmicpc.net/problem/15664

N과 M(11) : https://www.acmicpc.net/problem/15665

N과 M(12) : https://www.acmicpc.net/problem/15666

 

사용 알고리즘

Backtracking

 

풀이

후기

1. 이번 시리즈의 keypoint는 중복되는 숫자 처리이다.

 N과 M 시리즈 1(1 ~ 4)와 로직이 비슷하나 동일 숫자의 중복 처리가 더해져 조금 더 까다로웠다.

2. 백트레킹 유형을 통해 중복 수를 활용한 순열과 조합 등의 방식을 직접 구현 할 수 있었다.

 

15663. N과 M (9) 

1. 이 문제가 이후 문제 풀이에 가장 기초 틀이 되는 문제이다.

2. 입력 받은 수 중에서 중복 사용 없이 M개를 고른 수열을 출력한다.

 - 이때, 순서를 고려한 순열(Permutation)을 출력한다.

 - 때문에, 현재 깊이에서의 중복 여부 확인과 전체 깊이에서 사용 여부를 확인이 필요하다.

 - 기본적으로 현재 깊이에서의 중복 여부는 cur 변수를 새로 할당하여 진행하였다.

   cur은 해당 깊이에서만 사용되는 변수이며 sort 된 리스트에서 순열을 가져오기 때문에

   전에 사용한 수만 확인하기 위한 변수이다.

 - visited는 전체 깊이에서 사용되는 리스트이며 중복으로 나온 수도 관리하기 위해 인덱스로 접근하였다.

   visited로 관리하기 때문에 이전에 사용했던 수더라도 해당 인덱스 수가 아니면 다시 사용할 수 있다.

import sys
input = sys.stdin.readline


def backtracking(lst, visited):
    if len(lst) == M:
        print(*lst)
        return

    cur = 0
    for i in range(N):
        # 현재 깊이의 중복 여부 확인 & 총 깊이의 중복 여부 확인
        if num_lst[i] != cur and visited[i] == 0:
        
            # 백트레킹 들어가기 전 처리
            cur = num_lst[i]
            visited[i] = 1
            lst.append(num_lst[i])
            
            # 백트레킹
            backtracking(lst, visited)
            
            # 백트레킹 나온 후 처리
            lst.pop()
            visited[i] = 0


N, M = map(int, input().split())
num_lst = list(map(int, input().split()))
num_lst.sort()
visited = [0] * N
backtracking([], visited)

 

15664. N과 M (10) 

1. 이 문제는 5번 문제에서 순서를 고려하지 않은 문제이다.

2. 입력 받은 수 중에서 중복 없이 M개를 고른 수열을 출력한다.

 - 이때, 순서를 고려하지 않은 조합(Combination)을 출력한다.

 - 때문에, for문 흐름에 따라 진행을 위해 현재 기준점은 i를 들고 다니며 확인한다.

import sys
input = sys.stdin.readline


def backtracking(lst, order):
    if len(lst) == M:
        print(*lst)
        return

    cur = 0
    # 이전 백트레킹에서 진행한 다음 인덱스부터 진행
    for i in range(order, N):
        # 현재 깊이의 중복 여부 확인 & 총 깊이의 중복 여부 확인
        if num_lst[i] != cur and visited[i] == 0:
        
            # 백트레킹 들어가기 전 처리
            cur = num_lst[i]
            visited[i] = 1
            lst.append(cur)
            
            # 백트레킹 - 이때 다음 인덱스를 들고 진행
            backtracking(lst, i + 1)

            # 백트레킹 나온 후 처리
            lst.pop()
            visited[i] = 0


N, M = map(int, input().split())
num_lst = list(map(int, input().split()))
num_lst.sort()
visited = [0] * N
backtracking([], 0)

 

15665. N과 M (11) 

1. 이 문제는 9번 문제에서 중복을 고려하지 않은 문제이다.

2. 입력 받은 수 중에서 M개를 고른 수열을 출력한다.

 - 이때, 총 깊이에서의 중복도 가능하며 순서도 고려하여

   모든 가능한 순서쌍을 확인하는 데카르트 곱을 출력한다.

 - 때문에, if문 확인과 현재 기준점 i 모두 따로 확인할 필요 없이

   현재 깊이의 중복 여부만 확인하여 기본 백트레킹을 진행한다.

import sys
input = sys.stdin.readline


def backtracking(lst):
    if len(lst) == M:
        print(*lst)
        return

    cur = 0
    for num in num_lst:
        # 현재 깊이의 중복 여부만 확인
        if num != cur:
            cur = num
            lst.append(num)
            backtracking(lst)
            lst.pop()


N, M = map(int, input().split())
num_lst = list(map(int, input().split()))
num_lst.sort()

backtracking([])

 

15666. N과 M (12) 

1. 이 문제는 중복 없는 조합의 변형이다.

2. 입력받은 수 중에서 M개를 고른 수열을 출력한다.

 - 이때, 중복은 가능하지만, 순서는 고려되지 않은 자기 자신을 포함한 조합을 출력한다.

 - 때문에, 현재 기준점은 i를 들고 다니며 백트레킹을 진행 시

   다음 i+1부터 진행이 아닌 자기자신 i 부터 다시 진행되는 점이 기존 조합과 다르다.

import sys
input = sys.stdin.readline


def backtracking(lst, order):
    if len(lst) == M:
        print(*lst)
        return

    cur = 0
    # 이전 백트레레킹에서 진행된 인덱스부터 진행
    for i in range(order, N):
    
        # 현재 깊이의 중복 여부 확인
        if cur != num_lst[i]:
            cur = num_lst[i]
            lst.append(num_lst[i])
            # 백트레킹 - 현재 인덱스를 들고 진행
            backtracking(lst, i)
            lst.pop()


N, M = map(int, input().split())
num_lst = list(map(int, input().split()))
num_lst.sort()
backtracking([], 0)