https://www.acmicpc.net/problem/15663
문제
> N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
> N개의 자연수 중에서 M개를 고른 수열접근
여타 풀었던 N과 M문제들과 같지만
결과가 중복되면 안되기때문에 매 자릿수 마다 이전에 썼던 수를 기록해두고 같은 수를 쓰게 된다면 넘어간다.
또 모든 수 중 중복없이 써야하므로 기본적으로 매 재귀마다 입력받은 수 들 중 사용했다고 마킹 하지않은 수를 골라서 쓴다.
문제해결
> 입력받은 수를 저장할 num배열, 결과 수열을 저장할 result배열, 사용한 수 마킹할 visited배열을 선언한다.
> 수를 입력받고 사전순을 위해 num배열을 정렬해준다.
> NtoM메소드에 결과 수열 길이 0을 넣고 호출한다.
> 탈출 조건으로 수열의 길이가 M이 되면 깨고, 출력한다.
> 아니면 prev에 이전에 사용한 수를 기록해두며 매 재귀마다 0부터 N까지 반복한다.
> visited로 썼던 수 거나, 이전에 썼던 prev가 현재 뽑은 수라면 넘긴다.
> 아니라면 해당 수를 쓰고 마킹해두며 이전에 썼던 수를 갱신한다.
> 재귀로 다음 자리를 뽑기위해 들어간다.
> 재귀가 깨지면 다시 수를 쓸 수 있도록 마킹을 돌려놓는다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//15663번 N과 M (9)
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] num, result;
static boolean[] visited;
static public void NtoM(int rst) {
if(rst == M) {
for(int i : result) sb.append(i).append(' ');
sb.append('\n');
return;
}
int prev = 0;
for(int i = 0; i < N; i++) {
if(visited[i] || prev == num[i]) continue;
visited[i] = true;
result[rst] = num[i];
prev = num[i];
NtoM(rst + 1);
visited[i] = false;
}
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
num = new int[N];
result = new int[M];
visited = new boolean[N];
Arrays.fill(visited, false);
for(int i = 0; i < N; i++) num[i] = Integer.parseInt(st.nextToken());
Arrays.sort(num);
NtoM(0);
System.out.print(sb);
}
}
후기
고민을 좀 하게 됐던 문제였다. 바로 떠오르지 않아 조금 어려웠다.
