문제

BOJ 15650: N과 M (2) https://www.acmicpc.net/problem/15650

풀이

• 1부터 N까지의 수 중 오름차순이면서 M의 길이까지 나열 가능한 수열 을 구해야 한다.
• 사용할 dfs 함수에 시작할 수인 start 변수와 깊이를 나타낼 depth 변수를 입력값으로 준다.
• dfs함수 내 다시 dfs함수를 호출 할 때 start + 1과 depth + 1을 입력한다.
• 중복되는 수는 어차피 arr배열에 담을 수 없으므로 방문처리를 해주지 않아도 된다.

코드

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

public class Main {
	
	static int N, M;
	static int[] arr;
	
	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(1, 0); // 1 부터 시작 	
	}
	
	static void dfs(int start, int depth) {// 오름차순으로 출력해야 하기 때문에 어떤 수 부터 시작할지와 깊이를 넣어준다.
		if(depth == M) { // 종료 조건
			for(int i=0; i<M; i++) {
				System.out.print(arr[i]+" ");
			}
			System.out.println();
		}
		
		for(int i=start; i<=N; i++) { // 시작 수 부터 끝까지
			arr[depth] = i; // depth를 index로 하여 배열에 수를 넣는다.
			dfs(i + 1, depth + 1); // 1 더 큰 수를 시작으로하는 dfs를 호출한다.
		}
	}
	
}

정리

• 방문 처리를 해주지 않아도 되는지 판단하는 것을 배웠다.
• start 변수를 입력값으로 주어 해결하는 것을 배웠다.