백설공주와 일곱 난쟁이 [JAVA] (백준 3040)

 

문제

문제 링크 : https://www.acmicpc.net/problem/3040

3040번: 백설 공주와 일곱 난쟁이

문제 설명

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.

어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.

백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.

아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)

입력

총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.

출력

일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.

 

풀이

9명중에 7명의 합이 100이니깐 -> 2명의 합이 9개 합에서 100을 뺀 값이면 된다.

사실 ${}_9 \mathrm{ C }_2$의 경우 for문으로 간단하게 구현할 수 있지만 조합을 익히기 위해 조합으로 했다.

경우의 수는 ${}_9 \mathrm{ C }_7$나 ${}_9 \mathrm{ C }_2$같지만, 구현에 있어서는 ${}_9 \mathrm{ C }_2$이 훨씬 빠르기 때문에 이렇게 했다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

    //9개 모자 중 7개 -> 2개 아닌거 찾아야 함.
    static int round = 9;
    static int find = 2;
    static boolean stopsign = false;

   public static void main(String[] args) throws IOException{

      StringBuilder sb = new StringBuilder();
      BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));

      int sum = 0;
      ArrayList<Integer> hats = new ArrayList<Integer>();

      for(int i=0; i<round; i++) {
          int num = Integer.parseInt(br.readLine());
          hats.add(num);
          sum += num;
      }

      //2개 합이 이거여야함.
      sum = sum-100;
      int[] output = new int[find];
      Combination(hats, 0, round, find, 0, output, sum);


      //return answer
      for(int r : hats) {
          System.out.println(r);
      }
   }

   public static void Combination(ArrayList<Integer> array, int index, int n, int k, int t, int[] output, int sum) {
       if(stopsign) return;

       //selected all
       if(k == 0) {
           //만약 같으면
           if((sum - array.get(output[0])- array.get(output[1])) == 0) {
               stopsign = true;
               array.remove(output[0]);
               array.remove(output[1]-1);
           }
           return;
       }
       if(t == n) return;
       output[index] = t;
       Combination(array, index+1, n, k-1, t+1, output, sum);
       Combination(array, index, n, k, t+1, output, sum);
   }
}

 

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!