https://www.acmicpc.net/problem/15666
문제
> N개의 자연수와 자연수 M이 주어졌을 때,
아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
> N개의 자연수 중에서 M개를 고른 수열
> 같은 수를 여러 번 골라도 된다.
> 고른 수열은 비내림차순이어야 한다.
> 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
> 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.
> 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
> 수열은 사전 순으로 증가하는 순서로 출력해야 한다.접근
백트래킹으로 가능한 수열 조합을 탐색한다.
문제에서 조건으로 같은 수를 여러번 골라도 된다고 하였고, 비 내림차순이어야 한다고 했기 때문에 재귀로 넘기는 인덱스는 i로 넘겨 같은 수를 여러번 쓸 수 있게 해준다.
또 사용할 수를 입력받았을 때 오름차순으로 미리 정렬해 백트래킹에서 비 내림차순으로 뽑히도록 한다.
또 중복수열 출력을 못하도록 하였으므로, 매 자리의 수를 뽑을 때, prev라는 변수로 전 수열에서 해당 자리에 어떤 수를 썼는지 기록해두고 똑같은 수를 뽑는 경우를 방지해준다.
문제해결
> N과M을 입력받고 num배열에 N개의 수를 입력받는다.
> 비 내림차순을 위해 num배열을 정렬하고 결과 수열을 저장할 result 배열을 M크기로 선언한다.
> NtoM 메소드에 0,0을 파라미터로 호출한다.
> 메소드에선 입력으로 들어온 idx부터 수를 뽑으며, N번째 까지 모든 경우를 돈다.
> 이때 prev변수에 전 수열에서 뽑았던 수를 저장해두고 새 수를 뽑을 때 마다 비교한다.
> 같은 수를 뽑으면 스킵하고, 다른 수면 경우 의 수를 센다.
> result배열에 저장하고 prev를 갱신해주며 재귀를 들어간다.
> 같은 수를 사용할 수 있고 비내림차순이므로 동일한 인덱스인 i를 넘겨준다.
> rst == M에 걸리게되면, 즉 result배열의 크기가 M이 되면 결과를 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//15666번 N과 M(12)
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 public void NtoM(int idx, int rst) {
if(rst == M) {
for(int i : result) sb.append(i).append(' ');
sb.append('\n');
return;
}
int prev = 0;
for(int i = idx; i < N; i++) {
if(num[i] == prev) continue;
result[rst] = num[i];
prev = num[i];
NtoM(i, rst + 1);
}
}
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];
for(int i = 0; i < N; i++) num[i] = Integer.parseInt(st.nextToken());
Arrays.sort(num);
NtoM(0,0);
System.out.print(sb);
}
}
후기
NtoM 9번이 오히려 좀 더 까다로웠던것 같다.
