๐ข ๋ฐฑ์ค 15652๋ฒ - N๊ณผ M (4)

๐งฉ ๋ฌธ์ ์ค๋ช
- ์์ฐ์ N๊ณผ M์ด ์ฃผ์ด์ก์ ๋,
- 1๋ถํฐ N๊น์ง ์์ฐ์ ์ค M๊ฐ๋ฅผ ๋ฝ๋, ๊ฐ์ ์๋ฅผ ์ฌ๋ฌ ๋ฒ ๊ณจ๋ผ๋ ๋๊ณ
- ๋น๋ด๋ฆผ์ฐจ์(์ค๋ฆ์ฐจ์ ํฌํจ)์ธ ์์ด์ ๋ชจ๋ ๊ตฌํ๋ ๋ฌธ์ ์
๋๋ค.

๐ก ๋ฌธ์ ์กฐ๊ฑด ์์ฝ
์กฐ๊ฑด |
๋ด์ฉ |
์ซ์ ๋ฒ์ |
1 ~ N |
๋ฝ๋ ๊ฐ์ |
M๊ฐ |
์ค๋ณต ํ์ฉ |
โ
๊ฐ๋ฅ |
์์ ์ค์ |
โ ๋น๋ด๋ฆผ์ฐจ์๋ง ํ์ฉ |
์ ๋ ฌ |
์ค๋ฆ์ฐจ์ ๋๋ ๊ฐ์ ์ซ์ ํ์ฉ (ex. 1 1 2, 2 2 2 ๊ฐ๋ฅ) |
๐ฅ ์
๋ ฅ ์์
๐ค ์ถ๋ ฅ ์์
๐ง ํต์ฌ ์์ด๋์ด
์ด ๋ฌธ์ ๋ โ์ค๋ณต ์กฐํฉ (Combination with Repetition)โ ๋ฌธ์ ์
๋๋ค.
- ์ค๋ณต์ ํ์ฉ๋์ง๋ง ์์๋ง ์ ๋ ฌ๋ ํํ์ฌ์ผ ํ๊ธฐ ๋๋ฌธ์
start
๊ฐ์ ์ฌ๊ท๋ก ๋๊ฒจ์ฃผ๋ฉฐ ์ค๋ฆ์ฐจ์์ ์ ์งํฉ๋๋ค.
- ์ฆ, ์ด์ ์ ์ ํํ ์ซ์ ์ด์๋ถํฐ๋ง ๋ค์ ๊ณ ๋ฅผ ์ ์๋๋ก ํฉ๋๋ค.
โ
Java ์ฝ๋ ํ์ด
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Back_15652 {
public static int[] arr;
public static int N, M;
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());
arr = new int[M];
dfs(1, 0); // 1๋ถํฐ ์์, ๊น์ด๋ 0
}
private static void dfs(int start, int depth) {
if (depth == M) {
for (int i : arr)
System.out.print(i + " ");
System.out.println();
return;
}
for (int i = start; i <= N; i++) {
arr[depth] = i; // ํ์ฌ ์์น์ ์ซ์ ์ ์ฅ
dfs(i, depth + 1); // ์ค๋ณต ํ์ฉ โ i๋ถํฐ ๋ค์ ํ์
}
}
}
๐ ์ฝ๋ ํด์ค
1๏ธโฃ dfs(start, depth)
ํจ์
๋งค๊ฐ๋ณ์ |
์๋ฏธ |
start |
ํ์ฌ ์ ํ ๊ฐ๋ฅํ ์ต์ ์ซ์ (์ค๋ณต ํ์ฉ, ์ค๋ฆ์ฐจ์ ์ ์ง) |
depth |
ํ์ฌ๊น์ง ์ ํํ ์์ ๊ฐ์ (M์ ๋๋ฌํ๋ฉด ์ถ๋ ฅ) |
2๏ธโฃ ๊ธฐ์ ์กฐ๊ฑด
if (depth == M) {
for (int i : arr) System.out.print(i + " ");
System.out.println();
return;
}
- M๊ฐ์ ์๋ฅผ ๋ชจ๋ ๊ณจ๋์ผ๋ฉด ํ์ฌ ์กฐํฉ์ ์ถ๋ ฅํ๊ณ return.
3๏ธโฃ ์ค๋ณต ์กฐํฉ ๋ก์ง
for (int i = start; i <= N; i++) {
arr[depth] = i;
dfs(i, depth + 1); // ์ค๋ณต ํ์ฉ โ i๋ถํฐ ์์
}
- ์ค๋ณต ํ์ฉ์ด๊ธฐ ๋๋ฌธ์
dfs(i, depth + 1)
๋ก ํธ์ถ
- ์ผ๋ฐ ์์ด์ด๋ผ๋ฉด
dfs(i + 1, ...)
๋ก ํ๊ฒ ์ง๋ง, ์ฌ๊ธฐ์๋ ๊ฐ์ ์ซ์๋ ๋ค์ ์ฌ์ฉํ ์ ์์
๐ ์๊ฐ ๋ณต์ก๋
- ์ต์
์ ๊ฒฝ์ฐ
O(N^M)
์ ๋
N=7
, M=7
์ ๋๊น์ง๋ ์ถฉ๋ถํ ํ์ ๊ฐ๋ฅ
โ
์ ๋ฆฌ
ํญ๋ชฉ |
์ค๋ช
|
๋ฌธ์ ์ ํ |
๋ฐฑํธ๋ํน + ์ค๋ณต ์กฐํฉ |
์ค๋ณต ํ์ฉ |
O |
์ค๋ฆ์ฐจ์ ์ ์ง |
O (start ์ด์ฉ) |
DFS ํ์ ๋ฐฉ์ |
ํ์ฌ ์ซ์๋ถํฐ ๋ค์ ํ์ (์ค๋ณต ํ์ฉ) |
๋๊ธ๋จ๊ธฐ๊ธฐ