[알고리즘] 백준 일곱 난쟁이 2309번 JAVA

2021/01/05 - [코딩/알고리즘] - [알고리즘] 백준 골드바흐의 추측 6588번 JAVA

 

www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

문제중 일곱 난쟁이를 찾을 수 없는 경우는 없다.

라는 지문을 읽고 그러면 오름차순으로 정렬하고 7개 선택하면 되는거 아닌가?

 하고 코드를 짠 후 제출 했더니 틀렸습니다..

 

음..

합이 100이라는것을 내 스스로 생략해 버렸다.. 바보같은놈

 

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

public class Main_2309 {

    static int arry[] = new int[10];
    static boolean include[] = new boolean[10];
    static boolean answer = false;
    public static void main(String []args) {
        Scanner scanner = new Scanner(System.in);

        for(int i=1; i<=9; i++) {
            arry[i]=scanner.nextInt();
        }
        Arrays.sort(arry);//미리 정렬을 해줌
        sol(0,0,0);
        

    }

    public static void sol(int level,int sum,int count){
        if(answer) return; //결과를 출력했을 경우 true
        if(sum==100 && count==7) {
            output();
            answer=true; //결과 출력 이후 모든 유효한 노드들 방문 x
            return;
        }
        
        if(promising(level,sum,count)){
           include[level+1]=true;
           sol(level+1,sum+arry[level+1],count+1);

           include[level+1]=false;
           sol(level+1,sum,count);
       }
    }

    public static boolean promising(int level,int sum, int count) {
        if(level<9 && count<7 && sum+arry[level+1]<=100) return true; //유망한 조건
        else return false;
    }

    public static void output(){
        //include[i]=true인 경우만 출력
        for(int i=1; i<=9; i++) {
            if(include[i]) System.out.println(arry[i]);
        }
    }
}