Yunsu's Log

BOJ 15666: N과 M (12)

6 min read

Note

백트래킹을 활용하여 중복된 원소가 있는 배열에서 중복 선택이 가능한 비내림차순 조합을 생성하는 문제입니다.

문제 링크

문제 요약

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하세요.

  • N개의 자연수 중에서 M개를 고른 수열

  • 같은 수를 여러 번 골라도 됨

  • 고른 수열은 비내림차순이어야 함 (A₁ ≤ A₂ ≤ … ≤ Aₘ)

  • 중복되는 수열을 여러 번 출력하면 안 됨

  • 수열은 사전 순으로 증가하는 순서로 출력

  • 입력: N, M과 N개의 자연수

  • 출력: 조건을 만족하는 수열을 한 줄에 하나씩 출력

핵심 아이디어

비내림차순 조합 (중복 선택 가능)

이 문제는 비내림차순 조합을 생성하는 문제입니다:

  • 같은 수를 여러 번 선택할 수 있음
  • 수열이 비내림차순이어야 함
  • 중복 수열 제거 필요

핵심 포인트

  1. 중복 원소 제거: 입력 배열에서 중복을 제거하고 정렬
  2. 비내림차순 보장: start 파라미터를 사용하여 현재 선택한 인덱스부터 시작
  3. 중복 선택 가능: 같은 인덱스를 다시 선택할 수 있도록 i부터 시작

알고리즘 설계

1. 중복 제거 및 정렬

arr = list(map(int, input().split()))
arr = list(set(arr))  # 중복 제거
arr.sort()  # 정렬

2. 비내림차순 조합 생성

def dfs(start):
    if len(s) == M:  # M개를 모두 선택
        print(' '.join(map(str, s)))
        return
    
    for i in range(start, len(arr)):
        s.append(arr[i])
        dfs(i)  # i부터 시작 (중복 선택 가능)
        s.pop()

전체 코드

N, M = map(int, input().split())
 
arr = list(map(int, input().split()))
 
arr = list(set(arr))  # 중복 제거
arr.sort()  # 정렬
 
s = []
 
def dfs(start):
    if len(s) == M:
        print(' '.join(map(str, s)))
        return
    
    for i in range(start, len(arr)):
        # print('i:', i)
        s.append(arr[i])
        dfs(i)  # i부터 시작하여 중복 선택 가능
        s.pop()
 
dfs(0)

코드 설명

1. 입력 처리 및 전처리

N, M = map(int, input().split())
arr = list(map(int, input().split()))
 
arr = list(set(arr))  # 중복 제거
arr.sort()  # 정렬
  • 입력 배열에서 중복을 제거 (set 사용)
  • 정렬하여 사전순 출력 보장
  • 예: [4, 4, 2] → [2, 4]

2. 비내림차순 조합 생성

s = []
 
def dfs(start):
    if len(s) == M:  # 기저 조건
        print(' '.join(map(str, s)))
        return
    
    for i in range(start, len(arr)):
        s.append(arr[i])
        dfs(i)  # i부터 시작
        s.pop()
  • 기저 조건: M개를 모두 선택했으면 출력
  • 비내림차순 보장: start부터 시작하여 이전에 선택한 값보다 작은 값은 선택하지 않음
  • 중복 선택 가능: dfs(i)로 호출하여 같은 인덱스를 다시 선택할 수 있음

3. 동작 예시

입력: N=4, M=2, arr=[9, 7, 9, 1]

  1. 전처리: arr = [1, 7, 9] (중복 제거 및 정렬)
  2. 탐색 과정:
    • dfs(0): [1] 선택 → dfs(0): [1, 1] 출력
    • dfs(0): [1] 선택 → dfs(1): [1, 7] 출력
    • dfs(0): [1] 선택 → dfs(2): [1, 9] 출력
    • dfs(1): [7] 선택 → dfs(1): [7, 7] 출력
    • dfs(1): [7] 선택 → dfs(2): [7, 9] 출력
    • dfs(2): [9] 선택 → dfs(2): [9, 9] 출력

시간 복잡도

  • 시간 복잡도: O(중복 제거 후 원소 수^M)

    • 가능한 조합의 수: 중복 제거 후 원소 수에서 M개를 선택 (중복 선택 가능)
    • 각 조합 생성: O(M)

  • 공간 복잡도: O(M)

    • 현재 수열 저장: O(M)
    • 재귀 스택: O(M)

풀이 포인트

1. 중복 원소 제거

입력 배열에 중복된 원소가 있어도, 결과 수열의 중복만 제거하면 됩니다:

  • 입력 배열에서 중복을 제거하면 자동으로 중복 수열이 생성되지 않음
  • 예: [4, 4, 2] → [2, 4]로 변환하면 [2, 2], [2, 4], [4, 4]만 생성

2. 비내림차순 보장

start 파라미터를 사용하여 비내림차순을 보장:

  • 현재 선택한 인덱스 i부터 시작
  • 이전에 선택한 값보다 작은 값은 선택하지 않음
  • dfs(i)로 호출하여 같은 값을 다시 선택할 수 있음

3. 중복 선택 가능

dfs(i)로 호출하면:

  • 같은 인덱스 i를 다시 선택할 수 있음
  • 예: [1] 선택 후 dfs(0) 호출 → [1, 1] 생성 가능

관련 문제

그래프 뷰

백링크