백준 2309 / 일곱난쟁이

문제

풀이

설명

아홉 명의 난쟁이 중 일곱 명의 난쟁이를 찾는 문제이다.

• 9C2 = 36 즉, 경우의 수가 36가지 이다.
  사람이 구해도 크게 오래 걸리지 않는 경우의 수 이다.

모든 난쟁이 중에서 7명의 난쟁이가 아닌 2명의 난쟁이를 찾고 ( 9C2 = 36 )
나머지 난쟁이의 키의 합을 구하면 된다.

시간복잡도 : 두명을 고르는 경우의 수 O(N^2)이다.

코드

import java.util.*;

public class Num2309 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
        int n = 9;
        int[] a = new int[n];
        int sum = 0;
        
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            sum += a[i];
        }
        
        Arrays.sort(a);
        
        for (int i=0; i<n; i++) {
        	
            for (int j=i+1; j<n; j++) {
                if (sum - a[i] - a[j] == 100) {
                	
                    for (int k=0; k<n; k++) {
                        if (i == k || j == k) continue;
                        System.out.println(a[k]);
                    }
                    System.exit(0);
                }
            }
        }
	}
}

코드설명

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