백준 - 15652 N과 M (4) [백트래킹]

 

15652번: N과 M (4)

 

1. 문제 요약

1부터 N까지의 자연수를 사용하여 길이가 M인 수열을 생성하라

• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

2. 접근 방법

재귀 함수를 사용합니다.

15650(조합) 과 15651 을 적절히 섞으면 됩니다.

 

3. 파이썬

from sys import stdin
input = stdin.readline

def solution(start: int, depth: int):
    if depth == M:
        print(' '.join(map(str, arr)))
        return

    for i in range(start, N + 1):
        arr[depth] = i
        solution(i, depth + 1)

N, M = map(int, input().split())
arr = [0] * M
solution(1, 0)

 

4. 자바

static int N, M;
static int[] arr;
static StringBuilder sb = new StringBuilder();

static void solution(int start, int depth) {
    if (depth == M) {
        for (int i : arr) {
            sb.append(i).append(' ');
        }
        sb.append('\n');
        return;
    }

    for (int i = start; i <= N; i++) {
        arr[depth] = i;
        solution(i, depth + 1);
    }
}

// solution(1, 0);

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/15652.%E2%80%85N%EA%B3%BC%E2%80%85M%E2%80%85%EF%BC%884%EF%BC%89