[백준 2309, Java] 일곱 난쟁이

문제

www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

 

 

 

풀이1

- 9명의 난쟁이 중에서 7명을 뽑은 후, 7명의 키가 100이되는 경우를 탐색

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	public static int[] nineDwarf;
	public static int[] sevenDwarf;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		
		nineDwarf = new int[9];
		sevenDwarf = new int[7];
		for(int index = 0 ; index<nineDwarf.length; index++) {
			nineDwarf[index] = Integer.parseInt(br.readLine().trim());
		}
		
		selectOrNot(0, 0);
	}
	
	public static void selectOrNot(int index, int count) {
		if(count >=7) {
			// 일곱난쟁이 키의 합이 100이되는지 확인
			int heightSum = 0;
			for(int dwarfheight : sevenDwarf) {
				heightSum += dwarfheight;
			}
			
			if(heightSum == 100) {
				Arrays.sort(sevenDwarf);
				for(int dwarfheight : sevenDwarf) {
					System.out.println(dwarfheight);

				}
			}
		}
		else if(index>=nineDwarf.length) {
			return;
		}
		else {
			sevenDwarf[count]=nineDwarf[index];
			selectOrNot(index+1, count+1);
		
			selectOrNot(index+1, count);
		}
		
	}
}

 

풀이2

- 9명 중에서 난쟁이가 아닌 2명을 뽑아서 7명의 키가 100이되는지 확인

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static int[] nineDwarf;
    public static int[] sevenDwarf;
    public static int nineDwarfSum;

    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        nineDwarf = new int[9];
        sevenDwarf = new int[7];
        for(int index = 0 ; index<9; index++){
            nineDwarf[index] = Integer.parseInt(br.readLine());
            nineDwarfSum += nineDwarf[index];
        }
        findNoDwarf();
    }

    public static void findNoDwarf(){
        // 9명 중에 난쟁이가 아닌 2명을 뽑아서, 2명을 뺀 키의 합이 100 인지 확인
        Arrays.sort(nineDwarf);
        for(int i = 0; i < 9 ; i++){
            for(int j = i+1; j<9 ; j++){
                int sevenDwarfSum = nineDwarfSum - nineDwarf[i] - nineDwarf[j];
                if(sevenDwarfSum == 100){

                    for(int k = 0 ; k< 9; k ++){
                        if(k != i && k != j) {
                            System.out.println(nineDwarf[k]);
                        }
                    }
                    return;
                }

            }
        }
    }


}

 

 

* 보완 (2020. 12. 28)

main 에 함수로 구현하지 않았을 때, 아래와 같이 구현해서 틀렸다. 

for(int i = 0; i<9; i++){
            for(int j = i+1; j<9; j++){
                if(totalSum - heights[i] - heights[j]==100){
                    heights[i] = 0;
                    heights[j] = 0;
                    break;
                }
            }
        }

이유는 break를 했을 때 안쪽 for문만 빠져나오기 때문. 제대로 구현하기 위해서는 if문의 조건을 만족하는 경우 안쪽, 바깥쪽 for문 모두를 빠져나오게 해야한다

 

그래서 아래와 같이 플래그를 이용했다

boolean found = false;
        for(int i = 0; i<9; i++){
            for(int j = i+1; j<9; j++){
                if((totalSum - heights[i] - heights[j])==100){
                    heights[i] = 0;
                    heights[j] = 0;
                    found = true;
                    break;
                }
            }
            if(found) break;
        }

 

근데 이게 좀 지저분해 보여서 아래와 같이 함수로 구현했다.

public static void findStranger(int totalSum, int[] heights){
        for(int i = 0; i<9; i++){
            for(int j = i+1; j<9 ; j++){
                if(totalSum - heights[i]- heights[j]==100){
                    heights[i] = 0;
                    heights[j] = 0;
                    return;
                }
            }
        }
    }