D+6 백준 - 2309 일곱난쟁이

백준 2309 일곱난쟁이 - 브론즈 2

* 해당문제를 푸는 힌트는 9명의 난쟁이중 진짜 난쟁이는 7명 --> 이 7명을 찾는것이 아니라 해당하지 않는 2명의 난쟁이를 찾는것이다.

처음 7명을 찾고자했을때, ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ 9명에서 해당하는 7명을 찾으려면.. DFS, BFS를 사용해야하는건가? 도합 100이되는걸 찾도록...? 7중 for문을 사용할순 없으니.. 하고 생각했다.

하지만 해당문제를 뒤집어서 생각해보면 맞는 7명을 찾는것이 아니라 맞지않는 2명만 찾아내면 된다.

--> 이중 포문으로 해결가능함.

첫번째 for문에서 한 난쟁이를 빼고, 남은 sum값에서 두번째 난쟁이를 뺐을때 합이 100이되면 문제에 해당하는 답을 도출할 수 있다.

두 난쟁이를 찾으면 정렬 후 해당하는 값이 아닌 난쟁이의 키 값을 출력해주면 된다.

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

2309번: 일곱 난쟁이

 

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

public class Main {
   
    public static void main(String[] args) throws IOException {
    
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int [] height = new int[9];
        int sum =0; 
        for(int i=0; i<9; i++){
            st = new StringTokenizer(br.readLine());
            height[i] = Integer.parseInt(st.nextToken());
            sum +=height[i];
        }
        //System.out.println(sum);
        int n1 =0, n2 =0;
        for(int i=0; i<8; i++){
            int cal = sum; //항상 9난쟁이 다 더한값 유지
            cal -=height[i]; //cal에서 i를 뺌 
            n1 = height[i];
            for(int j=i+1; j<9; j++){
                if(cal-height[j] == 100){ //얘까지 뺐는데 100이네
                 n2 = height[j];
                    Arrays.sort(height); //정렬 해버려서..
                    for(int n=0; n<height.length; n++){
                    	if(height[n]!=n1 && height[n]!=n2){
                            System.out.println(height[n]);
                    	}
                    }
                    
                    return;
            }
        }
        
    }
   
}
}

 

** 정렬 Arrays.sort(배열) >> 맨날 까묵