[백준_2309] 일곱난쟁이

[1] 문제

[2] 문제 접근 방법

2-1) 1차 접근

 

단순히 오름차순 또는 내림차순으로 정렬하여, 문제를 풀려고 했지만 어떤 방식으로 나머지 값들을 제외하는지 찾지 못함.

 

2차 접근

 

내림차순으로 접근하던 도중 "출력 1"의 방법이 아닌 다른 방법을 찾았다고 생각하여 좋아하였지만 5명의 난쟁이로 구성된 정답이였다는 사실을 알게 되었다.

 

이를 통해, 반드시 7명이 필요하다는 사실을 잡고 문제를 풀어야 한다는 생각을 가지게 되었고! "9명인 경우, 2명만을 제외하면 된다"는 개념을 잡을 수 있었다.

 

이를 통해 난쟁이의 키를 모두 더한 값인 SUM에서 2명의 난쟁이를 뺏을 때의 값이 100이 나오는 경우를 찾아내는 방법을 고려하였고 그 결과는 아래의 코드와 같다.

 

[3] CODE 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = 9;
		int sum = 0;
		int tall [] = new int[n];
		int not [] = new int[2];
		
		for ( int i = 0; i < n; i++) {
			tall[i] = scan.nextInt();
			sum += tall[i];
		}
		
		Arrays.parallelSort(tall);
		
		for ( int i = 0; i < n; i++) {
			for ( int j = i+1; j < n; j++) {
				if ( sum - (tall[i] + tall[j]) == 100) {
					not[0] = tall[i];
					not[1] = tall[j];
				}
			}
		}
		
		for ( int i = 0; i < n; i++) {
			if ( tall [i] != not[0] && tall[i] != not[1]) {
				System.out.println(tall[i]);
			}
		}
		
	}
}