https://www.acmicpc.net/problem/15655
문제
> N개의 자연수와 자연수 M이 주어졌을 때,
아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
> N개의 자연수는 모두 다른 수이다.
> N개의 자연수 중에서 M개를 고른 수열
> 고른 수열은 오름차순이어야 한다.접근
백트래킹과 정렬을 이용한다. N개의 자연수를 배열에 입력받아 저장한 후, 오름차순으로 정렬해 준 뒤, 백트래킹으로 조합을 만들 때, 재귀로 현재 뽑은 수보다 더 큰수 중에서 뽑을 수 있도록 인덱스에 +1 해서 넘겨준다.
문제해결
> N과 M을 입력받고 입력받은 수를 num배열에 N크기로 저장하고 결과 배열을 M 크기로 result로 선언한다.
> N개의 자연수를 입력받아 저장하고, 오름차순 정렬한다.
> 재귀함수 NtoM에 초기값으로 0번 인덱스부터 0개의 원소를 가지도록 호출한다.
> 결과배열의 원소수 rst가 M개를 만족하면 재귀를 깨고, 뽑은 수열을 출력한다.
> 아니라면 수를 뽑기위해 idx로 들어온 수부터 반복문으로 가능한 경우를 뽑는다.
> 오름차순 수열이므로 같은 수는 사용할 수 없어서 i+1을 넘겨 현재 수보다 큰 수들 중 따지게 한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//28278번 스택 2
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] result;
static int[] num;
static void NtoM(int idx, int rst) {
if(rst == M) {
for(int i : result) sb.append(i).append(' ');
sb.append('\n');
return;
}
for(int i = idx; i < N; i++) {
result[rst] = num[i];
NtoM(i+1, 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());
num = new int[N];
result = new int[M];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) num[i] = Integer.parseInt(st.nextToken());
Arrays.sort(num);
NtoM(0, 0);
System.out.print(sb);
}
}
후기
어느정도 전역 선언도 익숙하고 재귀도 익숙해졌다.
