[BOJ 2309] 일곱 난쟁이 (java)

문제 링크

문제풀이

package basics_500;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ2309 {
	static int liarSum = 0;
	static int first = 0, second = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int sum = 0;
		// 9명의 키를 받을 배열
		int[] array = new int[9];
		boolean[] visited = new boolean[9];

		//난쟁이들 키 입력 받음 
		for (int i = 0; i < 9; i++) {
			array[i] = Integer.parseInt(br.readLine());
			sum += array[i];
		}
		//7명 난쟁이의 합은 100이기 때문 거짓말 하는 난쟁이들 2명의 키 합은 100을 뺀 나머지 
		liarSum = sum - 100;

		// 9명중 2명을 뽑기
		combination(array, visited, 0, array.length, 2);

		//오름차순으로 정렬 후 
		Arrays.sort(array);
		//거짓말하는 난쟁이들의 키를 제외하고 출력 
		for (int n : array) {
			if (n == first)
				continue;
			if (n == second)
				continue;
			System.out.println(n);

		}

	}
	
	//백트래킹 
	static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
		//r만큼 다뽑았다면(뽑을만큼 뽑았다면)   
		if (r == 0) {
			//뽑은 두명의 난쟁이가 거짓말하는 난쟁이인지 체크 
			findLiar(arr, visited, n);
			return;
		}
		//ex) 0번째 요소 뽑았으면 visited=true 해주고,
		// 그 다음 인덱스부터 시작하는 나머지 배열 요소중 다시 뽑기 
		for (int i = start; i < n; i++) {
			visited[i] = true;
			combination(arr, visited, i + 1, n, r - 1);
			visited[i] = false;
		}
	}

	static void findLiar(int[] arr, boolean[] visited, int n) {
		int sum = 0;
		for (int i = 0; i < n; i++) {
			if (visited[i] == true) {  
				sum += arr[i]; // 뽑힌 난쟁이 들의 키 합계를 구해서
				if (liarSum == sum) { //liarSum과 같다면, 거짓말하는 난쟁이들 발견 
					first = sum - arr[i];
					second = arr[i];
				}

			}

		}
	}

}