[BOJ] 2309. 일곱 난쟁이(조합 기본).java

#. Problem

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

* 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

아홉 난쟁이들 중 일곱 난쟁이를 뽑는 조합 문제다.

브루트 포스로 뽑을 수 있는 모든 경우의 수를 확인해본다.

단, 일곱 난쟁이가 다 뽑히고, 

뽑힌 난쟁이들 키의 합이 100이 만족될 때,

뽑힌 난쟁이들을 출력해주면 된다.

조합을 사용하지 않고 해결하는 방법도 있지만 

조합 연습을 위해 조합으로 해결해보자.

#. 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

import java.io.InputStreamReader; import java.util.Arrays; import java.io.BufferedReader; import java.io.IOException;   public class BOJ2309 {       static int N = 9, K = 100;     static int child[] = new int[N];     static int realChild[] = new int[7];     static boolean ckEnd = false;          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                  // 난쟁이들의 키 입력         for (int i = 0; i < N; i++)              child[i] = Integer.parseInt(br.readLine());                  process(0, 0, 0);     }     /**      * 일곱 난쟁이를 뽑을 수 있는 모든 경우의 수      * @param idx 난쟁이의 위치      * @param cnt 뽑은 난쟁이의 수      * @param sum 뽑힌 난쟁이들 키의 합      */     public static void process(int idx, int cnt, int sum) {         // 키의 합이 100인 일곱 난쟁이가 다 뽑힌 상태면         // 더이상 경우의 수를 확인할 필요가 없으므로 return         if(ckEnd) return;         // 일곱 난쟁이가 뽑히면         if(cnt == 7) {             // 뽑힌 난쟁이들의 키의 합이 100이 되는지 확인             if(sum == K) {                 // 키의 합이 100이라면 난쟁이들의 키를 오름차순으로 정렬 후 출력                 Arrays.sort(realChild);                 for (int i = 0; i < 7; i++)                      System.out.println(realChild[i]);                 ckEnd = true;             }             return;         }         if(idx >= N) return;         // 일곱 난쟁이가 뽑히기도 전에 키의 합이 100을 초과하면 return         if(sum > K) return;                  // 이 난쟁이가 진짜? 한번 뽑아볼까?         realChild[cnt] = child[idx];         process(idx + 1, cnt + 1, sum + child[idx]);         // 이 난쟁이는 안 뽑고 넘어갈래         process(idx + 1, cnt, sum);     }      }   Colored by Color Scripter

cs