코테/백준
[백준/JAVA] 15651번: N과 M (3)
imname1am
2023. 6. 5. 18:07
반응형
🔺 문제
15651번: N과 M (3)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[] A;
static StringBuilder sb = new StringBuilder();
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());
A = new int[M];
dfs(0);
System.out.println(sb);
}
private static void dfs(int depth) {
if(depth == M) {
for(int val : A) {
sb.append(val + " ");
}
sb.append("\n");
return;
}
for(int i = 1 ; i <= N ; i++) {
A[depth] = i;
dfs(depth + 1);
}
}
}
|
cs |
✅ 해결 아이디어
✔ 백트래킹 (DFS) : 중복 가능
- 같은 수를 여러번 골라도 된다. 즉, 중복을 고려하지 않아도 되므로 방문 여부를 판단할 필요가 없다.
오... dfs 메소드를 private으로 선언하니 메모리랑 시간이 조금 더 줄어들었다
💬 느낀 점
엥.. 솔직히 N과 M (1) (2)보다 얘가 더 쉬웠다,,,
(사실 이래놓고 조금 헤맴)
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 8.29 |
(+ 2회독 : 8. 29)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[] A, result;
static StringBuilder sb = new StringBuilder();
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());
A = new int[N];
for(int i = 0 ; i < N ; i++) {
A[i] = i + 1;
}
result = new int[M];
back(0);
System.out.println(sb);
}
private static void back(int depth) {
if(depth == M) {
for(int i : result) sb.append(i).append(" ");
sb.append("\n");
return;
}
for(int i = 0 ; i < N ; i++) {
result[depth] = A[i];
back(depth + 1);
}
}
}
|
cs |
어랏.. 메모리 사용량을 2배 이상 줄이다...
반응형