15651문제 N과M 3번(브루트포스) Java

문제

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

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

입력

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

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

출처: <https://www.acmicpc.net/problem/15651>

15651번: N과 M (3)

 

 

##문제이해##

기존 N과M1번에서는 중복방지를 위해 자기자신을 선택한 후 boolean[] visit을 이용해서 방문여부를 체크하고 이미 넣은값이라면 추가하지 않았는데. 여기서는 중복을 허용하기때문에 그 부분을 제외하면 되는 문제였다!

##코드##

import java.util.Scanner;

public class boj_15651 {
	static Scanner sc;
	static int N; //숫자의 범위. ex 4라면 1,2,3,4 까지의 범위.
	static int M; //조합하는 숫자의 갯수 ex) 4라면 총 만드는 숫자가 1 2 3 4 와같이 4개의 수를 가진다.
	static int[] arr;
	static StringBuffer sb;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); //숫자의 범위. ex 4라면 1,2,3,4 까지의 범위.
		M = sc.nextInt(); //조합하는 숫자의 갯수 ex) 4라면 총 만드는 숫자가 1 2 3 4 와같이 4개의 수를 가진다.
		arr = new int[M];
		sb = new StringBuffer();
		dfs(0);
		System.out.println(sb);
	}
	public static void dfs(int depth){
		// 재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
		if (depth == M) {
			for (int val : arr) {
				sb.append(val + " ");
			}
			sb.append('\n');
			return;
		}
	 
	 
		for (int i = 0; i < N; i++) {
			//중복체크를 할 필요가 없어서 방문여부체크를 없애고 그냥 출력시킴.
			arr[depth] = i+1;
			dfs(depth + 1);	
		}
		return;
		
		
	}

}