Yunsu's Log

BOJ 15652: N과 M (4)

6 min read

Note

백트래킹을 활용하여 1부터 N까지의 자연수에서 중복 선택이 가능한 비내림차순 조합을 생성하는 문제입니다.

문제 링크

문제 요약

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

  • 1부터 N까지 자연수 중에서 M개를 고른 수열

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

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

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

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

  • 입력: 자연수 N, M (1 ≤ M ≤ N ≤ 8)

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

핵심 아이디어

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

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

  • 1부터 N까지의 자연수에서 선택
  • 같은 수를 여러 번 선택할 수 있음
  • 수열이 비내림차순이어야 함

핵심 포인트

  1. 비내림차순 보장: start 파라미터를 사용하여 현재 선택한 값부터 시작
  2. 중복 선택 가능: 같은 값을 다시 선택할 수 있도록 i부터 시작
  3. 자연스러운 사전순: 1부터 N까지 순서대로 선택하므로 자동으로 사전순

알고리즘 설계

1. 초기화

arr = []

2. 비내림차순 조합 생성

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

전체 코드

N, M = map(int, input().split())
 
arr = []
 
def dfs(value):
    if len(arr) == M:
        print(' '.join(map(str, arr)))
        return
    
    for i in range(value, N + 1):
        arr.append(i)
        dfs(i)  # i부터 시작하여 중복 선택 가능
        arr.pop()
 
dfs(1)

코드 설명

1. 초기화

N, M = map(int, input().split())
arr = []
  • N: 1부터 N까지의 자연수
  • M: 선택할 개수
  • arr: 현재 선택한 수열을 저장하는 리스트

2. 비내림차순 조합 생성

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

3. 동작 예시

입력: N=4, M=2

탐색 과정:

  • dfs(1): [1] 선택 → dfs(1): [1, 1] 출력
  • dfs(1): [1] 선택 → dfs(2): [1, 2] 출력
  • dfs(1): [1] 선택 → dfs(3): [1, 3] 출력
  • dfs(1): [1] 선택 → dfs(4): [1, 4] 출력
  • dfs(2): [2] 선택 → dfs(2): [2, 2] 출력
  • dfs(2): [2] 선택 → dfs(3): [2, 3] 출력
  • dfs(2): [2] 선택 → dfs(4): [2, 4] 출력
  • dfs(3): [3] 선택 → dfs(3): [3, 3] 출력
  • dfs(3): [3] 선택 → dfs(4): [3, 4] 출력
  • dfs(4): [4] 선택 → dfs(4): [4, 4] 출력

출력:

1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

시간 복잡도

  • 시간 복잡도: O(N^M)

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

  • 공간 복잡도: O(M)

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

풀이 포인트

1. 비내림차순 보장

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

  • 현재 선택한 값 i부터 시작
  • range(value, N + 1)로 이전에 선택한 값보다 작은 값은 선택하지 않음
  • 예: [2] 선택 후 dfs(2) 호출 → [2, 1]은 생성되지 않음

2. 중복 선택 가능

dfs(i)로 호출하면:

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

3. 자연스러운 사전순

1부터 N까지 순서대로 선택하므로 자동으로 사전순이 됩니다:

  • 별도의 정렬 과정 불필요
  • range(value, N + 1)로 이미 정렬된 순서

다른 구현 방법

값을 직접 사용하는 대신 인덱스를 사용하는 방법도 있습니다:

N, M = map(int, input().split())
 
arr = list(range(1, N + 1))
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)
        s.pop()
 
dfs(0)

이 방법은 BOJ 15666과 유사한 구조입니다.

관련 문제

그래프 뷰

백링크