[BOJ_Python] 15654 ~ 15657. N과 M 시리즈 2 (5 ~ 8)

문제

N과 M(5) : https://www.acmicpc.net/problem/15654

N과 M(6) : https://www.acmicpc.net/problem/15655

N과 M(7) : https://www.acmicpc.net/problem/15656

N과 M(8) : https://www.acmicpc.net/problem/15657

 

사용 알고리즘

Backtracking

 

풀이

후기

1. 이번 시리즈는 N과 M 시리즈 1(1 ~ 4)와 로직은 동일하나 연속된 수가 아닌 입력받은 수로 진행하는 문제이다.

때문에 로직에 큰 변화없이 입력받은 수를 가지고 저번과 동일하게 진행하였다.

2. 백트레킹 유형을 통해 입력받은 수로 순열과 조합 등의 방식을 직접 구현 할 수 있었다.

15654. N과 M (5) 

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

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

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

 - 때문에, 현재 리스트를 들고 다니며 다음 넣을 수가 리스트에 있는지 여부를 확인하는 if문이 필요했다.

import sys
input = sys.stdin.readline


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

    for i in num_lst:
        if i not in lst:
            lst.append(i)
            backtracking(lst)
            lst.pop()


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

 

15655. N과 M (6) 

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

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

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

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

import sys
input = sys.stdin.readline


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

    for cur in range(i, N):
        lst.append(num_lst[cur])
        backtracking(cur + 1, lst)
        lst.pop()


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

 

15656. N과 M (7) 

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

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

 - 이때, 중복도 가능하며 순서도 고려하여 모든 가능한 순서쌍을 확인하는 데카르트 곱을 출력한다.

 - 때문에, if문 확인과 현재 기준점 i 모두 따로 확인할 필요 없이 기본 백트레킹을 진행한다.

import sys
input = sys.stdin.readline


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

    for cur in num_lst:
        lst.append(cur)
        backtraking(lst)
        lst.pop()


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

 

15657. N과 M (8) 

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

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

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

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

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

import sys
input = sys.stdin.readline


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

    for cur in range(i, N):
        lst.append(num_lst[cur])
        backtracking(cur, lst)
        lst.pop()


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