[BOJ-2309][완전 탐색/조합] 일곱 난쟁이 - Java

문제 바로가기

2309번: 일곱 난쟁이

오랜만입니다,,,, ^^

 

카카오 코테를 거나하게 말아먹고....

라인 코테는 붙...었지만 필기가 남아 있고....

 

 

다시 PS 를 열심히 해봅시다.

이 문제는 아아주 쉬운 문제랍니다.

모든 경우를 다 봐주면 되는데, 조건이 전혀 까다롭지 않아서 쉽게 풀 수 있습니다.

 

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		List<Integer> dwarfs = new ArrayList<>();
		int total = 0;
		for(int i = 0; i < 9; i++) {
			dwarfs.add(Integer.parseInt(br.readLine()));
			total += dwarfs.get(i);
		}
		// 조합으로 두 개 골라서 뺀게 100 되는 경우를 찾자

		outer:
		for(int i = 0; i < 9; i++) {
			int first = dwarfs.get(i);
			for(int j = i + 1; j < 9; j++) {
				int second = dwarfs.get(j);
				if(first + second + 100 == total) {
					dwarfs.remove((Integer)first);
					dwarfs.remove((Integer)second);
					break outer;
				}
			}
		}

		Collections.sort(dwarfs);
		
		for(int i : dwarfs) System.out.println(i);
	}
}

 

아홉 명의 난쟁이들 중에서 거짓말하는 못된 두 놈을 골라야 합니다.

착한 일곱 난쟁이들의 키를 모두 더하면 100인걸 아니깐 두 놈을 골라서(조합) 키의 총합에서 그 둘의 키를 빼서 100인 경우만 찾아주면 되는 것이죵.

 

보통 조합을 만들 때는 재귀를 많이 사용하져. 경우에 따라서 총 몇놈을 골라줄지 유동적인 경우가 많기 때문입니다.

 

하지만 이 문제는 깔끔히 두 놈만 골라주면 됩니다. 고로 2중 for문으로 끝낼 수 있답니다.

 

first + second + 100 == total을 만족한다면 가차없이 first와 second를 쫓아내 줍시다.

그러고 남은 착한 난쟁이들을 사이좋게 정렬시키고 출력하면 끝!

 

 

화이팅!!!!