[BOJ]2309번: 일곱 난쟁이(java, c++)

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

2309번: 일곱 난쟁이

 

 

import java.io.*;
import java.util.Arrays;
 
public class Main {
    
     public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        // 입력, 총합sum 구하기
        int[] arrDwarfs = new int[9];
        int sum = 0;        
        for (int i = 0; i < 9; i++) {
            arrDwarfs[i] = Integer.parseInt(br.readLine());
            sum += arrDwarfs[i];
        }
        
        // 오름차순 정렬
        Arrays.sort(arrDwarfs);
        
        // 총합 - 2개요소 = 100 인 것을 구하기
        for (int i = 0; i < arrDwarfs.length; i++) {
            for (int j = i + 1; j < arrDwarfs.length; j++) {
                
                if (sum - arrDwarfs[i] - arrDwarfs[j] == 100) {
                    for (int k = 0; k < arrDwarfs.length; k++) {
                        
                        if (k == i || k == j) {
                            continue;
                        }
                        bw.write(arrDwarfs[k] + "\n");
                    }
                    bw.flush();
                    return;
                }
            }
        }
    }
}

 

c++소스

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    const int dwarfNum = 9;
    int dwarf[dwarfNum];
    
    // 입력. 난쟁이 키 총합 계산
    int sum = 0;
    for (int i = 0; i < dwarfNum; i++)
    {
        cin >> dwarf[i];
        sum += dwarf[i];
    }
 
    // 오름차순 정렬
    sort(dwarf, dwarf + dwarfNum);
 
    for (int i = 0; i < dwarfNum; i++)
    {
        for (int j = i + 1; j < dwarfNum; j++)
        {
            // 총합 - 난쟁이키 2명 = 100 일때 출력 후 종료.
            if (sum - (dwarf[i] + dwarf[j]) == 100)
            {
                for (int k = 0; k < dwarfNum; k++)
                {
                    if (k == i || k == j)
                    {
                        continue;
                    }
                    cout << dwarf[k] << '\n';
                }
                return 0;
            }
        }
    }
 
    return 0;
}

 

조합으로 풀기도 했는데, 속도는 위에 3중 포문 돌린것과 같았다. 

입력 갯수가 많아지면 조합 또는 정렬이 더 적절할 것 같다. 

 

TIP

일곱 난쟁이의 키의 합이 100이 됨

 

9명 중 7명의 난쟁이의 키의 합이 100이라면,

총합에서 2명 키를 빼면 100이 된다라는 말과 같다.

 

문제를 조금만 더 생각하면 코드가 간결해진다!