[Java+Python]15652번, N과 M(4), 중복조합

Java+Python으로 순열/조합/중복순열/중복조합 구현하기

 

[Java+Python]15649번, N과 M(1), 순열

[Java+Python]15650번, N과 M(2), 조합

[Java+Python]15651번, N과 M(3), 중복순열

[Java+Python]15652번, N과 M(4), 중복조합

 

문제

 

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
• 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

입력

 

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 

중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

풀이

 

중복순열을 풀 때와 마찬가지로 이미 방문한 노드를 다시 방문할 수 있도록

 

isVisited 배열과 검증을 제거해주면 된다.

 

그러니까 순열, 조합의 DFS만 제대로 외우고 있어도 어지간한 백트래킹은 풀이할 수 있다는 뜻.

 

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Prob15652 {
	static int n;
	static int m;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[m];

		dfs(1, 0);

		System.out.println(sb);
	}

	private static void dfs(int start, int depth) {
		if (depth == m) {
			for (int num : arr) {
				sb.append(num).append(' ');
			}
			sb.append('\n');
			return;
		}

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

다음은 파이썬이다.

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
lst = [0 for _ in range(m)]


def dfs(start, depth):
    if depth == m:
        for num in lst:
            print(num, '', end='')
        print()
        return

    for i in range(start, n + 1):
        lst[depth] = i
        dfs(i, depth + 1)


dfs(1, 0)