백준저지 2309번 일곱 난쟁이

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

2309번: 일곱 난쟁이

 

제출 날짜: 2021년 8월 27일 금요일

 

 

 

생각

조합으로 풀었는데 막판에 틀렸다. 잘못한 게 없어서 질문글을 검색해보니 나처럼 93%쯤에 틀린 사람이 있었다. 해당 글(https://www.acmicpc.net/board/view/57583)의 답변을 보고 실행해보니 실제로 답이 여러 개인 경우, 나는 답 여러 개를 출력하고 있다는 걸 알게 되었다. 문제에도 '가능한 정답이 여러 가지인 경우에는 아무거나 출력한다'라고 적혀있는데 그걸 보고도 그냥 답이 여러 개일 수가 있구나 하고 넘겨서 발생한 문제였다. 다음부터는 문제를 조금 더 꼼꼼히 읽어야겠다.

 

 

 

코드

// 출처: 백준저지 2309번 일곱 난쟁이 https://www.acmicpc.net/problem/2309

import java.util.Arrays;
import java.util.Scanner;

public class BOJ2309 {

    static int[] dwarf = new int[9]; // 입력받을 아홉 난쟁이
    static int[] seven = new int[7]; // 임시로 저장할 일곱 난쟁이
    static int[] answer = new int[7]; // 답이 될 일곱 난쟁이

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 9; i++) {
            dwarf[i] = sc.nextInt();
        }
        Arrays.sort(dwarf); // 입력받은 아홉 난쟁이 정렬
        combination(0, 0, 0); // 조합

        for (int a : answer) { // 답 출력
            System.out.println(a);
        }

    }

    private static void combination(int cnt, int start, int sum) {
        if (cnt == 7) {
            if (sum == 100) { // 합이 100일 때 답에 해당 일곱 난쟁이를 저장
                for (int i = 0; i < 7; i++) {
                    answer[i] = seven[i];
                }
            }
            return;
        }

        for (int i = start; i < 9; i++) {
            seven[cnt] = dwarf[i];
            combination(cnt + 1, i + 1, sum + dwarf[i]);
        }
    }
}