[BOJ - JAVA] 15651 - N과 M 3(백트래킹)

# 주소

www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

# 문제

 

 

# 문제 분석

이번에도 백트래킹을 이용하여 문제를 해결해야 합니다. 이번엔 저번 문제처럼 간단히 해결할 수 있습니다.

다만 중복을 허용하여 경우의 수를 따지는 것이므로 코드를 작성할 때 arr의 값은 i로 통일하되 arr[depth +1]만 해주어 

이전 문제와 마찬가지로 depth == M일 때에만 출력하고 return 하는 방식을 취했습니다. 

 

따라서 dfs함수를 작성하는 방식에 있어서 인수를 이전 문제들과 달리 depth 한 개만 받으면 된다는 차이점이 있습니다.

그리고 Scanner, Print 방식을 사용하면 시간 초과가 뜨므로 이번에는 StringBuilder 방법으로 문제를 풀었습니다.

다음에는 이것보다 메모리 시간을 더 단축시킬 수 있는 StringBuffered 방식으로 풀이하겠습니다.

 

# 코드 해설

import java.util.Scanner;
 
public class Main {
 
	public static int[] arr;
	public static int N, M;
    public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
        
		Scanner in = new Scanner(System.in);
 
		N = in.nextInt();
		M = in.nextInt();
 
		arr = new int[M];
        
		dfs(0);
        System.out.print(sb);
	}
 
	public static void dfs(int depth) {
 
		if (depth == M) {
			for (int val : arr) {
				sb.append(val + " ");
			}
			sb.append('\n');
			return;
		}
        
		for (int i = 1; i <= N; i++) {
 
			arr[depth] = i;
			dfs(depth + 1);
		}
	}
}