[백준] 15652 : N과 M (4) - JAVA [자바]

안녕하세요.

오늘은 N과 M (4) 문제를 풀어보도록 하겠습니다.

 

 

 

📌 접근

길이가 M인 수열을 만들면 되므로 dfs를 사용하였습니다.

길이 M 달성 시, result에 결과를 추가하고 재귀를 종료하게 됩니다..

 

dfs는 이전에 추가한 숫자를 알 수 있게 before를,

현재 만든 문자열을 뜻하는 str를 인자로 갖게 구조를 만들었습니다.

 

💻 풀이

// hyeblee
import java.io.*;
import java.util.*;


public class Main {
	public static int N, M;
	public static StringBuilder result = new StringBuilder("");

	public static void dfs(int depth, String str, int before) {
		if (depth == M) {
			result.append(str + "\n");
			return;
		}
		for (int i = 1; i <= N; i++) {
			if (before <= i)
				dfs(depth + 1, str + i + " ", i);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		dfs(0, "", 0);
		System.out.println(result);
	}
}

🤔 고민했던 점 & 어려웠던 부분

 

1 1 2 와 1 2 1이 같은 조합이라는 것을 생각하지 못했다. 그래서

 

1 1 3 -> 1 2 2 가 나와야하는데

1 1 3 -> 1 2 1 이 나왔다.

 

어떻게 해결할까 고민하다가, dfs에 before 인자를 추가했다.

다음에 추가할 숫자는 이전에 추가한 숫자보다 크거나 같기 때문이다.

 

 

하지만 dfs에 현재의 결과를 뜻하는 str를 계속 들고다니는 것보다,

(함수에 인자가 3개나 되니까. . .)

int 배열을 사용하여 풀이하는게 더 깔끔한 것 같다.

 

개선한 코드

// 개선한 코드
import java.io.*;
import java.util.*;

public class Main {
	public static int N, M;
	public static int[] nums;

	public static void dfs(int depth, int before) {
		if (depth == M) {
			for (int v : nums) {
				System.out.print(v + " ");
			}
			System.out.println();
			return;
		}
		for (int i = before; i <= N; i++) {
			nums[depth] = i;
			dfs(depth + 1, i);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		nums = new int[M];
		dfs(0, 1);
	}
}