Sign in Subscribe
PS

[PS] BOJ / N과 M

Minjun Kim

• 5 min read
[PS] BOJ / N과 M
Thumbnail: Photo by Daniel Dan (Unsplash)

N과 M 문제 시리즈의 풀이를 모아왔습니다.

N과 M (6) / BOJ 15655

  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 오름차순
  • 주어지는 $N$개의 자연수는 모두 서로 다른 수
  • 같은 수 중복 사용 X

고른 수열이 오름차순으로 나오기 위해서는 입력 받은 수를 정렬한 뒤 순차적으로 백트래킹을 통해 수열을 구성하면 된다. 또, 이전 칸에서 사용한 수 보다 큰 수들만 뒤에서 사용할 수 있도록 백트래킹의 매개변수를 통해 관리해 주었다.

같은 수를 중복해서 사용하지 않기 위해, 별도의 배열을 활용해 각 수를 앞서 사용했는지 검사하고 사용하지 않은 수들만 뒤에서 사용할 수 있도록 했다.

input = open(0).readline
N, M = map(int, input().split())
numbers = sorted(map(int, input().split()))
used = [False] * N
arr = [0] * M

def backtracking(depth, start):
    if depth == M:
        print(" ".join(map(str, arr)))
        return
    
    for n in range(start, N):
        if not used[n]:
            used[n] = True
            arr[depth] = numbers[n]
            backtracking(depth + 1, n + 1)
            used[n] = False
    arr[depth] = ""

backtracking(0, 0)

boj 15655

N과 M (7) / BOJ 15656

  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 오름차순
  • 주어지는 $N$개의 자연수는 모두 서로 다른 수
  • 같은 수 중복 사용 O

같은 수를 중복해서 사용할 수 있기 때문에, 굳이 각 수의 사용 여부를 검사할 필요가 없다. 오름차순으로 수열을 만들기 위해서는 N과 M (6)에서 사용한 것처럼 $N$개의 자연수를 미리 정렬하고, backtracking 함수로 재귀를 이어갈 때 이전에 사용한 수보다 큰 수만 다음 칸에 쓸 수 있게 참조해주면 된다.

input = open(0).readline
N, M = map(int, input().split())
numbers = sorted(map(int, input().split()))
arr = [0] * M

def backtracking(depth):
    if depth == M:
        print(" ".join(map(str, arr)))
        return
    
    for n in range(N):
        arr[depth] = numbers[n]
        backtracking(depth + 1)
    arr[depth] = ""

backtracking(0)

boj 15656

N과 M (8) / BOJ 15657

  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 비 내림차순 ($i < j$ 일 때, $A_{i} \leq A_{j}$)
  • 주어지는 $N$개의 자연수는 모두 서로 다른 수
  • 같은 수 중복 사용 O

같은 수를 중복해서 사용할 수 있기 때문에, 굳이 각 수의 사용 여부를 검사할 필요가 없다.

비 내림차순으로 수열을 만들기 위해서는 N과 M (6)에서 사용한 것처럼 $N$개의 자연수를 미리 정렬하고, backtracking 함수로 재귀를 이어갈 때 이전에 사용한 수보다 같거나 큰 수만 다음 칸에 쓸 수 있게 참조해주면 된다.

input = open(0).readline
N, M = map(int, input().split())
numbers = sorted(map(int, input().split()))
arr = [0] * M

def backtracking(depth, start):
    if depth == M:
        print(" ".join(map(str, arr)))
        return
    
    for n in range(start, N):
        arr[depth] = numbers[n]
        backtracking(depth + 1, n)
    arr[depth] = ""

backtracking(0, 0)

boj 15657

N과 M (10) / BOJ 15664

  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 비 내림차순 ($i < j$ 일 때, $A_{i} \leq A_{j}$)
  • 주어지는 $N$개의 자연수는 같은 수가 포함될 수 있음
  • 같은 수 중복 사용 X (입력으로 주어진 만큼만 사용 가능)

​이전 문제들과는 달리 입력으로 주어지는 자연수 중에 같은 수가 여러 번 주어질 수 있다. 따라서, 각 수가 입력에서 주어진 횟수를 기록한 뒤, 백트래킹 과정에서 주어진 횟수 이하로 각 수를 사용하게끔 구현했다.

비 내림차순으로 수열을 만들기 위한 방법은 N과 M (8)과 같다.

input = open(0).readline
N, M = map(int, input().split())
numbers_cnt = [0] * 10001
for n in map(int, input().split()):
    numbers_cnt[n] += 1
numbers_used = [0] * 10001
arr = [0] * M

def backtracking(depth, start):
    if depth == M:
        print(" ".join(map(str, arr)))
        return
    
    for n in range(start, 10001):
        if numbers_used[n] < numbers_cnt[n]:
            numbers_used[n] += 1
            arr[depth] = n
            backtracking(depth + 1, n)
            numbers_used[n] -= 1
    arr[depth] = ""

backtracking(0, 1)

boj 15664

N과 M (11) / BOJ 15665

  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 비 내림차순 ($i < j$ 일 때, $A_{i} \leq A_{j}$)
  • 주어지는 $N$개의 자연수는 같은 수가 포함될 수 있음
  • 같은 수 중복 사용 O

N과 M (10)과 같이 입력 받은 자연수에도 중복이 있을 수 있고, 결과 수열에도 같은 수를 중복해서 쓸 수 있다. 따라서, 입력 받은 자연수가 몇 번 등장했는지는 기록하는 대신, 그냥 입력 받은 자연수의 종류만 기억하고 백트래킹을 진행했다.

비 내림차순으로 수열을 만들기 위한 방법은 N과 M (8)과 같다.

input = open(0).readline
N, M = map(int, input().split())
numbers = {}
for n in sorted(map(int, input().split())):
    numbers[n] = numbers.get(n, False) or True

arr = [0] * M

def backtracking(depth):
    if depth == M:
        print(" ".join(map(str, arr)))
        return
    
    for n in numbers:
        arr[depth] = n
        backtracking(depth + 1)
    arr[depth] = ""

backtracking(0)

boj 15665