[백준]13-백트래킹/3-N과 M(3)/15651 풀이 JAVA

문제

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

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

입력

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

 

출력

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

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

 

풀이(JAVA)

	import java.io.*;
	import java.util.*;
	public class Main {
	private static int n, m; // 입력받을 N, M
	private static int[] num; // num[0] ~ num[m]까지가 출력할 1줄
	private static StringBuilder sb = new StringBuilder();
	// DFS(깊이 우선 탐색)
	public static void dfs(int depth) {
	if (depth == m) { // 깊이가 m이 되면 (num[0]~num[m]까지 다 채웠을 때) 출력
	for (int temp : num)
	sb.append(temp).append(' ');
	sb.append('\n');
	return;
	}
	for (int i = 0; i < n; i++) { // number뷰터 n까지 반복(오름차순)
	num[depth] = i + 1; // num 배열에 숫자 채우기
	dfs(depth + 1); // 깊이 + 1하며 재귀 호출
	}
	return;
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// 입력
	StringTokenizer st = new StringTokenizer(br.readLine()); br.close();
	n = Integer.parseInt(st.nextToken());
	m = Integer.parseInt(st.nextToken());
	// num 배열 생성
	num = new int[m];
	// 시작
	dfs(0);
	// 출력
	System.out.println(sb);
	}
	}

view raw 15651.java hosted with ❤ by GitHub

---

예전 코드들을 의식하지 말자고 생각한지 n초만에... 성공^^

아자자