문제

BOJ 15651: N과 M (3) https://www.acmicpc.net/problem/15651

조건 확인

• 1 ~ N 까지의 수를 조합한다.
• 길이가 M 인 조합이다.
• 중복해서 조합할 수 있다.

풀이

• DFS를 사용하여 1부터 중복이 가능한 조합으로 M개를 뽑는다.
• 중복이 가능하므로 방문 처리를 해주지 않아도 된다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N, M;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		sc.close();
		
		arr = new int[N];
		
		dfs(0);
		System.out.println(sb);
	}
	
	static void dfs(int depth) {
		if(depth == M) {
			for(int i=0; i<M; i++) {
				sb.append(arr[i]+" ");
			}
			sb.append("\n");
			return;
		}
		
		for(int i=1; i<=N; i++) {
			arr[depth] = i;
			dfs(depth + 1);
		}
	}
	
}

정리

• 처음 코드를 작성했을 때 밑의 코드에서 return;을 해주지 않아 ArrayIndexOutOfBoundsException이 발생했다.

if(depth == M) {
			for(int i=0; i<M; i++) {
				sb.append(arr[i]+" ");
			}
			sb.append("\n");
			return; // 해줘야 탈출함
}

• 출력에서 시간이 좀 걸릴 것 같으면 StringBuilder를 사용하면 된다.