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

# 주소

https://www.acmicpc.net/submit/15652/33669457

로그인

 

# 문제

 

# 문제 해석

저번 문제처럼 간단했다. 이번엔 중복을 허용하여 비내림차순(중복허용하여 오름차순)으로 경우의 수를 구하는 것이다.

특히, t = i라고 선언하고 for문을 i = t 부터 시작점을 잡아야 두번째 항, 세번째 항의 값을 구할 때 이전 위치의 항보다 

작지 않은 값을 가질 수 있다. 코드로 보면 빠르게 이해할 수 있을 것이다.

 

import java.util.*;

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(1,0);
        System.out.print(sb);
	}
 
	public static void dfs(int t, int depth) {
		if (depth == M) {
			for (int val : arr) {
                
				sb.append(val + " ");
			}	
			sb.append('\n');
			return;
		}
        
		for (int i = t; i <= N; i++) {
			t = i;

			arr[depth] = t;
			dfs(t, depth + 1);
			
		}
	}
}

 

다른 사람의 풀이를 보니 for문에서 i = t로 잡고 dfs(i, depth + 1) 로 입력하여 풀었다. 

성능에서 큰 차이는 없으나 코드를 줄이는 방법에 대해서 아직 공부할 부분이 많다. BufferedReader로 풀려고 했는데

습관이 되어 Scanner방식으로 푼 것 같다.