[백준_15651번] N과 M (3)

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

15651번: N과 M (3)

[문제]

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

[입력 조건]

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

 

[코드]

import java.util.Scanner;

public class BaekJoon_15651 {
	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(n,m,0);
		System.out.println(sb);
	}
	
	/*
	 * 해당 문제는 중복을 허용하며, 조건을 만족하는 수열을 출력해야 하기 때문에
	 * 해당 노드를 방문했는지 체크하는 visited 없이 깊이만 증가시키며
	 * 모든 경우의 수를 배열에 저장하면 된다.
	 */
	static void dfs(int n, int m, int depth) {
		if(m==depth) {
			for(int i=0;i<m;i++) sb.append(arr[i]+" ");
			sb.append("\n");
			return;
		}
		for(int i=1;i<=n;i++) {
			arr[depth]=i;
			dfs(n,m,depth+1);
		}
	}
}

 

[고찰]

 이번 문제는 N과 M의(1)과 비슷한 문제이다. 앞선 두 문제를 통해 해당 유형과 같은 유형에 익숙해진 탓인가 빠르게 해결 가능했다. 맨 처음 문제에 노드 방문 처리만 삭제하면 정답 처리가 되는 문제이기 때문에 빠르게 구현할 수 있었다.