728x90
https://www.acmicpc.net/problem/15666
15666번: N과 M (12)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
이 문제는 중복되는 수열을 제거하고 또한 이전에 앞자리에 쓰인 숫자는 사용이 안되게 만드는 것이다. 하지만 자기자신을 사용한 경우는 출력한다. 잘 알아듣지 못할 수도 있어서 I/O 예제를 가져왔다.
여기서 사용해야할 것은 중복을 제거하기 위한 메서드 수행시마다 확인할 tmp와 시작지점을 바꿀 at을 사용한다.
물론 변수는 다른걸 사용해도 상관없다.
그렇게 해서 dfs메서드를 재귀로 돌리는 동안에는 at을 변화시키면 자기 자신을 포함한 수열의 경우는 구할 수 없음으로, at은 재귀가 끝날 때마다 증가시킨다. N과 M문제는 재귀를 이해하는 것이 중요한 문제이기 때문에 크게 설명할 것이 없다.
모두 코드를 직접 손으로 써서 해보거나, 디버깅을 이용해서 확인해 보는 것이 이해가 빠를 것이다.
그래서 정답 코드는 아래와 같다.
package backjoon.b15666;
import java.io.*;
import java.util.*;
public class b15666 {
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());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
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;
int[] answer;
boolean[] check;
StringBuilder sb;
public Graph(int n, int m, int[] arr) {
this.n = n;
this.m = m;
this.arr = arr;
sb = new StringBuilder();
check = new boolean[n];
answer = new int[m];
}
public void dfs(int at, int depth){
if(depth==m){
for(int i : answer){
sb.append(i).append(" ");
}
sb.append("\n");
return;
}
int tmp = 0;
for(int i=at; i<n; i++){
if(check[i] || tmp==arr[i]){
continue;
}
answer[depth]=arr[i];
tmp=arr[i];
dfs(i,depth+1);
at++;
}
}
}
드디어 N과 M을 다 부쉈다. 확실히 풀고나니 조금 구조가 이해되고, 조합도 이해한 것 같다. 이제 다른 문제들도 더 풀어보면서 알고리즘 지식을 더욱 키워야겠다.
728x90
