문제

BOJ 15652: N과 M (4) https://www.acmicpc.net/problem/15652

조건 확인

• 1부터 N까지의 자연수 중에서 M개를 골라 출력한다.
• 같은 수를 여러 번 골라도 된다.(중복 허용)
• 비내림차순 즉, 오름차순으로 출력한다.
• 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

• DFS 재귀호출을 사용한다.
• 중복이 허용 되므로 반복문 내에서 i값을 그대로 인자로 넘겨 재귀호출 해준다.

코드

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);
		
	}
	
	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();
			return;
		}
		
		for(int i=start; i<=N; i++) {
			arr[depth] = i;
			dfs(i, depth + 1); // 중복 허용(자기 자신도 출력)이기 때문에 i를 넣어준다.
		}
		
	}
	
}

정리

• 중복 허용이라 재귀 호출 시 i값을 그대로 인자로 넘겨줘야한다.
• 종료 조건에 return;을 넣어 종료시켜주자.