[BOJ] 15649. N과 M(1)(순열 기본).java

#. Problem

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

* 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개를 고른 수열을 찾는 순열 문제이다.

순열 : 서로 다른 n개의 원소 중에서 중복을 허락하지 않고, 순서를 생각하며 r개를 일렬로 나열하는 수열

순열은 순서를 생각하기때문에

1 2

2 1

이 두 수열이 다르다고 받아들여진다.

쉽게 생각하면

1 2 는 오름차순

2 1 은 내림차순

이렇게 순서가 있기 때문에..!

반대로 조합은 

1 2

2 1 

이 같다고 받아들여진다.

조합은 순서를 생각하지 않기 때문에,

1과 2를 골라서 나온 순열이라면 다 같은 경우라는 것이다.

#. 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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ15649_v2 {          static int N, M;     static int arr[];     static boolean visited[];     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());         // init         arr = new int[N];         visited = new boolean[N];         sel = new int[M];         for (int i = 0; i < N; i++)              arr[i] = i+1;                  process(0);         System.out.println(sb);     }          public static void process(int cnt) {         // M개의 자연수를 골랐다면          if(cnt == M) {             int x = 0;             // 선택된 자연수를 buffer에 저장             for (int j = 0; j < N; j++) {                 if(visited[j]) {                     sb.append(sel[x++] + " ");                 }             }             sb.append('\n');             return;         }         for (int i = 0; i < N; i++) {             // 중복을 허용하지 않으므로             // 사용되지 않은 자연수일 경우             if(!visited[i]) {                 // 이 자연수를 사용해보자.                 visited[i] = true;                 // 사용된 자연수를 배열에 저장                 sel[cnt] = arr[i];                                  // 위 자연수를 사용했으므로 cnt + 1 해주고, 재귀함수로 넘겨주자.                 process(cnt+1);                                  // 이 자연수를 사용하지 않을 경우.                 visited[i] = false;             }         }     } }   Colored by Color Scripter

cs

속도 향상을 위해 stringbuilder를 사용하느라 코드가 뭔가 길어보이네..