[백준_15652번] N과 M (4)

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

[문제]

 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.(길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.)

 

[입력조건]

 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

[코드]

import java.util.Scanner;

public class BaekJoon_15652 {
	static int[] arr;
	static StringBuilder sb=new StringBuilder();
	public static int n,m;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		m=sc.nextInt();
		
		arr=new int[m+1];
		dfs(1,0);
		System.out.println(sb);
	}
	
	/*
	 * 첫 번째 값 이상의 값을 가진 수열들만 출력하야하기 때문에
	 * 첫 번째 값을 저장한 at 변수를 매개변수로 하는 함수를 재귀호출 한다. 
	 */
	static void dfs(int at, int depth) {
		if(m==depth) {
			for(int i=0;i<m;i++) {
				sb.append(arr[i]+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i=at;i<=n;i++) {
			arr[depth]=i;
			dfs(i,depth+1);
		}
	}
}

 

[고찰]

 이번 문제는 N과 M의 마지막 문제였다. 15650과 같이 첫 번째 수열의 값을 저장하는 start 변수를 사용하여 start 이상의 값들만 출력해주도록 처리하면 정답인 간단한 문제였다. 앞선 문제들을 통해 DFS의 개념을 익힐수 있는 시간이었다.