[BOJ] 15652. N과 M(4)(중복조합 기본).java

#. Problem

https://www.acmicpc.net/problem/15652

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

N개의 자연수 중에서 M개를 고른 수열인데, 같은 수를 여러 번 골라도 되고,

고른 수열은 비내림차순이라고 했다.

즉, 중복조합을 구하는 문제이다!

이미 고른 자연수를 또 고를 수 있어서

1부터 3까지의 자연수 중 2개를 고르는 중복조합이라고 하면

3 2

1 1 
1 2 
1 3 
2 2 
2 3 
3 3

와 같은 결과를 얻을 수 있는 것이다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ15652 {          static int N, M;     static int arr[];     static int sel[];     static StringBuilder sb = new StringBuilder();          public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                  StringTokenizer st = new StringTokenizer(br.readLine(), " ");         N = Integer.parseInt(st.nextToken());         M = Integer.parseInt(st.nextToken());         arr = new int[N];         sel = new int[M];         for (int i = 0; i < N; i++)              arr[i] = i+1;                  process(1, 0);         System.out.println(sb);     }          public static void process(int idx, int cnt) {         if(cnt == M) {             int x = 0;             out: for (int j = 0; j < N; j++) {                 sb.append(sel[x++] + " ");                 if(x == M) break out;             }                          sb.append('\n');             return;         }         // 중복조합이므로 자기 자신idx부터 자연수를 고를 수 있다.         for (int i = idx - 1; i < N; i++) {             // 중복이 허용되므로 해당 자연수가 사용되었는지 확인할 필요가 없다.             sel[cnt] = arr[i];             process(i + 1, cnt+1);         }     } } Colored by Color Scripter

cs