일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 동적계획법
- 백준
- 알고리즘공부
- dp
- 빅오 표기법
- 백준알고리즘
- 무료코딩강의
- Java개념
- 개발공부
- 자바
- 백트래킹
- 알고리즘
- 브루트포스
- ☆
- 자바의정석연습문제풀이
- 자바의정석연습문제
- 자바개념
- BFS
- 코딩공부
- ★
- 무료개발강의
- 자바의정석
- java
- 백준자바
- 시간 복잡도
- 백준단계별로풀어보기
- 자바공부
- 백준9단계
- 다이나믹 프로그래밍
- dfs
- Today
- Total
더 많이 실패하기
공부 163일차: 백준 15666번 N과 M (12) 자바 java 본문
15666 N과 M (12)
https://www.acmicpc.net/problem/15666
15666번: N과 M (12)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
백준 15666번 문제 N과 M (12)
문제

과정 생각해보기
https://gimbalja.tistory.com/305
공부 162일차: 백준 15665번 N과 M (11) 자바 java
15665 N과 M (11) https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서
gimbalja.tistory.com
https://gimbalja.tistory.com/304
공부 161일차: 백준 15664번 N과 M (10) 자바 java
15664 N과 M (10) https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서
gimbalja.tistory.com
12번째 문제는 11번째 문제에서 조건이 하나 추가되었다
- N개의 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
결국 10번, 11번 문제를 결합하면 쉽게 풀리는 문제다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public static void DFS(int start, int depth) throws IOException{
if(depth == m) {
for(int val : arr) {
bw.write(val+" ");
}
bw.newLine();
return;
}
int before = 0;
for(int i = start; i < n; i++) {
if(before != nums[i]) { // 중복처리
visited[i] = true; // 비내림차순처리 1
arr[depth] = nums[i];
before = nums[i];
DFS(i, depth+1);
visited[i] = false; // 비내림차순처리 2
}
}
}
|
cs |
before 변수로 중복 체크하고
visited[]로 비내림차순으로 들어올 수 있도록 한다
정답 인정 코드
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int[] arr, nums;
static boolean[] visited;
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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];
nums = new int[n];
visited = new boolean[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(nums);
DFS(0, 0);
bw.flush();
bw.close();
}
public static void DFS(int start, int depth) throws IOException{
if(depth == m) {
for(int val : arr) {
bw.write(val+" ");
}
bw.newLine();
return;
}
int before = 0;
for(int i = start; i < n; i++) {
if(before != nums[i]) { // 중복처리
visited[i] = true; // 비내림차순처리 1
arr[depth] = nums[i];
before = nums[i];
DFS(i, depth+1);
visited[i] = false; // 비내림차순처리 2
}
}
}
}
|
cs |
계속 반복되는 문제 패턴
N과 M 마지막 문제까지 다 풀었다
DFS에 친숙해진 것 같아 기쁘다
'알고리즘 > 백준' 카테고리의 다른 글
공부 165일차: 백준 10973번 이전 순열 자바 java (0) | 2023.01.11 |
---|---|
공부 164일차: 백준 10972번 다음 순열 자바 java (1) | 2023.01.10 |
공부 162일차: 백준 15665번 N과 M (11) 자바 java (0) | 2023.01.08 |
공부 161일차: 백준 15664번 N과 M (10) 자바 java (1) | 2023.01.07 |
공부 160일차: 백준 15663번 N과 M (9) 자바 java (0) | 2023.01.06 |