[BOJ] 15666 N과 M (12) - JAVA

1. 문제

15666번: N과 M (12)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

---

2. 풀이

N과 M (9) 풀이와 비슷하다.

ststic 변수

int[] arr	입력받은 전체 숫자들
int[] picked	뽑은 숫자
int N,M	주어진 수
StringBuilder sb	답으로 출력할 문자열

 

Main

문제 입력값을 모두 저장한 뒤 배열을 정렬한다.

조합 함수를 호출하고, sb를 출력한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   N = Integer.parseInt(st.nextToken());
   M = Integer.parseInt(st.nextToken());

   arr = new int[N];
   st = new StringTokenizer(in.readLine());
   for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
   Arrays.sort(arr);

   picked = new int[M];
   sb = new StringBuilder();
   pick(0,0);

   System.out.print(sb);
}

 

중복 조합

M개 뽑았을 때 picked에 저장된 순서대로 sb에 더하고 끝낸다.

 

뽑을 때, i=idx부터 시작하는 이유는 비내림차순이기 때문이다. 정렬된 배열이라 idx부터 시작해야 arr[idx]보다 같거나 큰 값을 고를 수 있다.

 

입력으로 주어지는 수는 모두 자연수이기 때문에 before을 0으로 두고 시작한다.
만약 이미 뽑은 위치의 숫자이거나 이전 수와 동일한 숫자면 뽑지 않고 지나간다.
cnt가 같은 상태에서(=같은 차례의 숫자를 뽑을 때) 동일한 숫자를 두 번 이상 뽑으면 그 이후의 과정이 모두 중복되기 때문이다.
picked[cnt]에 arr[i]를 저장하고 before을 arr[i]로 교체한다.

그 후 재귀호출한다.

public static void pick(int cnt, int idx){
   if(cnt==M){
      for(int i=0;i<M;i++){
         sb.append(picked[i]).append(' ');
      }
      sb.append('\n');
      return;
   }

   int before = 0;
   for(int i=idx;i<N;i++){
      if(before == arr[i]) continue;
      picked[cnt] = arr[i];
      before = arr[i];
      pick(cnt+1,i);
   }
}

---

3. 결과