[BOJ] 2309번 일곱 난장이

문제

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

2309번: 일곱 난쟁이

 

 

풀이

문제를 다시 말하면 9명의 난쟁이 중, 7명씩 골라서 키를 다 더해봤을 때 100이 되는 경우를 고르는 문제이다.

다만, 가능한 정답이 여러 가지인 경우에는 아무거나 출력하는 조건이 있으므로, 답을 찾으면 다른 예시를 찾는 경우를 줄이기 위해 체크하는 변수를 두어 처리해준다.

 

import java.util.*;
public class Main {
    static Scanner scan = new Scanner(System.in);
    static int f_dw[] = new int[7];
    static int dwarfs[] = new int[9];
    static boolean chk = false;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        for(int i=0;i<9;i++)
            dwarfs[i] = scan.nextInt();
        find_dwarf(0,0);
    }
    public static void find_dwarf(int st, int depth) {
        if(chk)//이미 찾았으면 더 안찾고 리턴
            return;
        if(depth == 7) {
            int sum = 0;
            for(int i=0;i<7;i++)
                sum+=f_dw[i];
            if(sum==100) {
                chk = true;//찾았으면 계속 찾기 않게 표시해줌
                Arrays.sort(f_dw);
                for(int i=0;i<7;i++)
                    System.out.println(f_dw[i]);
            }
            return;
        }
        for(int i=st;i<9;i++) {
            f_dw[depth] = dwarfs[i];
            find_dwarf(i+1,depth+1);
        }
    }
}