[백준] 일곱 난쟁이 (Java)

 

주소

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

 

주의점

아홉 난쟁이 중 일곱 난쟁이만 산출한다.

일곱 난쟁이 키의 합은 100 이다.

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

 

알고리즘 선택과 근거

브루트포스 알고리즘

- 문제의 달성 조건이 명확하다.

- 정답이 여러개일 수 있으나 풀이의 수가 제한되어 있다.

 

풀이

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int sum = 0;
        int[] arr = new int[9];
        // 스파이 난쟁이 초기값은 배열 인덱스 벗어난 값으로 설정
        int spy1 = 10;
        int spy2 = 11;
        // 백트래킹용 boolean
        boolean check = false;
        
        // sum 에 입력값 누적
        for (int i = 0; i < 9; i++) {
            arr[i] = sc.nextInt();
            sum += arr[i];
        }
        
        Arrays.sort(arr);
        
        for (int i = 0; i < arr.length - 1; i++) {
            
            // 백트래킹 (해를 찾았으면 벗어나기)
            if (check) {
                break;
            }
            for (int j = i + 1; j < arr.length; j++) {
				
                // sum - 두 난쟁이가 100 인 해를 찾으면 변수에 기록하고 break
                if (sum - (arr[i] + arr[j]) == 100) {
                    spy1 = i;
                    spy2 = j;
                    check = true;
                    break;
                }
            }
            
        }
        
        for (int i = 0; i < 9; i++) {
            // 진짜 난쟁이만 출력
            if (i != spy1 && i != spy2) {
                System.out.println(arr[i]);
            }
        }
    }
}