https://www.acmicpc.net/problem/15655
15655번: N과 M (6)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열
www.acmicpc.net
이 문제는 15654번과 15650번을 합친 문제라고 생각할 수 있다. 풀이는 간단하다. 입력 받은 배열을 이용하여 dfs를 구현하는 것이다.
중요한 것은 중복이 없고 앞자리 수보다 작은 수는 오지 않게 만든다는 것이다. 그럼으로 15650번과 마찬가지로 at 변수를 사용하여 시작지점을 설정하여 출력하면 된다.
15650번과 같은 방식과 15654의 배열 이용 방법을 이용한 것이기 때문에 설명은 생략하려고 한다.
아래의 링크를 통해 자료를 확인해보면 좋을 것 같다.
https://parkjunbackend.tistory.com/22
b15650번, b15651번, b15652번
https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
parkjunbackend.tistory.com
https://parkjunbackend.tistory.com/25
b15654번
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수
parkjunbackend.tistory.com
정답코드는 아래와 같다.
package backjoon.b15655;
import java.io.*;
import java.util.*;
public class b15655 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
st=new StringTokenizer(br.readLine());
int[] arr = new int[N];
for(int i=0; i<N; i++){
arr[i]= Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
Graph g = new Graph(N,M,arr);
g.dfs(0,0);
System.out.println(g.sb);
}
}
class Graph{
int n;
int m;
int[] arr;
Stack<Integer> answer;
StringBuilder sb;
public Graph(int n, int m , int[] arr){
this.n = n;
this.m = m;
this.arr = arr;
answer = new Stack<>();
sb = new StringBuilder();
}
public void dfs(int at, int depth){
if(depth==m){
for(int i : answer){
sb.append(i).append(" ");
}
sb.append("\n");
return;
}
for(int i=at; i<n; i++){
answer.add(arr[i]);
dfs(at+1,depth+1);
answer.pop();
at++;
}
}
}