Notice
Recent Posts
Link
- Today
- Total
hye-log
[백준]15652번 N과 M(4)(JAVA) 본문
0. 문제 링크
https://www.acmicpc.net/problem/15652
15652번: N과 M (4)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
1. 문제 설명
1) 1부터 N까지 자연수 중에서 중복 가능한 M개를 고른 수열 구하기 -> 중복 조합
2. 입출력
// input
4 2
// output
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
3. 코드
import java.io.*;
import java.util.StringTokenizer;
public class b15652 {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
// 1. 입력
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 2. N개 중에 중복 없이 M개 고르기
int[] arr = new int[N]; // 원본 배열
int[] sel = new int[M]; // 선택 배열
for(int n = 0; n < N; n++) { // 원본 배열 생성
arr[n] = n+1;
}
recursive(arr, sel, 0, 0);
bw.flush(); // flush로 시간 초과 해결
bw.close();
}
// arr : 원본 배열, sel : 선택 배열, idx : 원본 배열 인덱스, k : 선택 배열 인덱스
private static void recursive(int[] arr, int[] sel, int idx, int k) throws IOException {
// basis part
if(k == sel.length) { // M개 골랐으면 출력
for(int s = 0; s < sel.length; s++) {
sb.append(sel[s] + " ");
}
sb.append("\n");
bw.write(sb.toString());
sb.setLength(0);
return;
}
// inductive part
for(int i = idx; i < arr.length; i++) {
sel[k] = arr[i]; // 하나 선택하기
recursive(arr, sel, i, k+1);
}
}
}
실행 결과
4. 회고
1) 중복 조합 재귀로 구현
2) N이 커질수록 연산 시간이 길어지므로 BufferedWriter를 이용하여 시간 초과 해결
5. Github
https://github.com/iihye/Algorithm/blob/main/Baekjoon/b15652.java
728x90
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준]11660번 구간 합 구하기 5(JAVA) (0) | 2023.08.06 |
---|---|
[백준]11659번 구간 합 구하기 4(JAVA) (0) | 2023.08.06 |
[백준]15651번 N과 M(3)(JAVA) (0) | 2023.08.06 |
[백준]15650번 N과 M(2)(JAVA) (0) | 2023.08.06 |
[백준]15649번 N과 M(1)(JAVA) (0) | 2023.08.06 |
Comments