[BOJ] 15651. N과 M(3)(중복순열 기본).java

#. Problem

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

* 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 2 3

이 주어졌을 때,

2개를 골라 만들 수 있는 중복 순열은

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

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 47

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ15651 {          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;         // 처음에 0개의 자연수를 고른 상태로 시작         process(0);         System.out.println(sb);     }          public static void process(int cnt) {         // M개의 자연수를 모두 골랐다면         // 고른 자연수들을 buffer에 저장         if(cnt == M) {             int x = 0;             for (int j = 0; j < N; j++) {                 sb.append(sel[x++] + " ");                 if(x == M) break;             }             sb.append('\n');             return;         }         for (int i = 0; i < N; i++) {             // 중복 순열이므로 해당 숫자가 사용되었는지 확인할 필요 없음             // 그냥 바로 해당 자연수를 사용해버리기!             sel[cnt] = arr[i];             process(cnt+1);         }     } } Colored by Color Scripter

cs