백준 - 3040/백설 공주와 일곱 난쟁이

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

12467

8332

6998

70.071%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

7
8
10
13
15
19
20
23
25

---

9개의 모자중 7개의 모자를 골라 모자에 적힌 수를 더한합이 100이 되는 모자들을 출력하는 문제이다.

모자를 선택하기만 하면 되므로 조합을 생각하여 풀어보았다.

 

1. 조합을 이용한 풀이

 

package practice;

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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



        List<Integer> hats = new ArrayList<>(); // 모자의 숫자들을 저장할 리스트, 또는 int[]로 구현한다.

        for(int i=0;i<9;i++)
        {
            hats.add(Integer.parseInt(br.readLine())); // 입력된 값을 받아 int로 바꾸고 저장.
        }
        bw.flush();
        //9개중 7개의 모자를 가지고 100을 만들어야한다. 순서와 상관없이 7개를 뽑는것이므로 조합을 이용한다.
        //조합은 방문배열을 이용하여 뽑는경우 , 안뽑는경우를 만들면서 모든경우를 확인하는식으로 구현한다.

        boolean[] visited = new boolean[9]; // 뽑았는지 안 뽑았는지를 저장할 boolean 배열, 모자의 총 개수를 크기로 가진다.
        //뽑은 모자의 숫자들을 출력해야하므로 , true인 인덱스들을 이용하여 어떤 모자가 뽑혔는지 출력할때 쓸수도있다.

        int count  =0 ; //모자를 몇개선택했는지를 저장할 변수.
        int sum = 0 ; // 모자를 선택하면서 전체합은 몇인지 저장할 변수.

        combination(hats,visited,count,sum,0);

        bw.close();


    }
    public static void combination(List<Integer> hats, boolean[] visited,int count,int sum,int start) throws IOException
    {
        if(count == 7) //모자를 7개를 선택했을경우
        {
            if(sum == 100) // 합계가 100인경우 , 모자들을 출력하고 프로그램 종료
            {
                for(int i=0;i<9;i++)
                {
                    if(visited[i])
                    {
                        bw.write(hats.get(i)+"\n");
                    }
                }
                bw.close();
                System.exit(0);
            }
            return;
        }
        else if(sum > 100) //선택한 모자가 7개도 안됬는데 총합이 100을 넘으면 볼것도없으므로 해당 재귀메소드 종료.
        {
            return;
        }

        for(int i=start;i<9;i++) //뽑을수있는 전체 목록에서 선택하고,안하고를 해야하니까 반복문사용,
        // 순열에서는 1,2,3 과 1,3,2가 다르다. 조합에서는 1,2,3 이랑 1,3,2가 똑같기 떄문에 인덱스의 시작을 count로 해준다. (count는 몇개뽑았는지 체크하는 변수이다)
        // count부터 시작하는 이유는 0~count까지의 인덱스의 경우의수는 이미 만들었기 떄문이다. -> 1,2,3,4,5에서 3개 조합으로 뽑는 결과를 보면 각 자릿수에서 고정해서 올라가면서 경우의수를 만드는걸확인가능
        // 예) 3개를 뽑아야하고 1,2,3을 뽑았다고 했을시 [1,2,3] 출력후 visited[2] = false 처리된다.
        // 인덱스의 시작을
        {
            if(!visited[i]) //선택하지않았던거라면 선택하고 combination메소드를 재귀적으로 실행하고 , 선택했던걸 취소한다.
            {
                visited[i] =true;
                combination(hats,visited,count+1,sum+hats.get(i),i+1);
                visited[i] = false;
            }
        }

    }



}

순열,중복순열,조합,중복조합 정리

 

조합은 순열과 달리 뽑았던 요소구성이 또 나오면안된다.

그러므로 뽑을 전체 목록에서 반복문을 돌릴때 시작인덱스를 뽑았던 갯수로 시작한다. 뒤의 조합만 신경쓰게끔.