[BOJ] 2309 일곱 난쟁이

#include <iostream>
#include <algorithm>
using namespace std;

int height[9];

int main(void)
{
    int i, j, n, k;
    int sum = 0, find = 0;

    for (i = 0; i < 9; i++) {
        scanf("%d", &height[i]);
        sum += height[i];
    }
    sort(height, height + 9);
    for (i = 0; i < 9; i++) {
        sum -= height[i];
        for (j = i + 1; j < 9; j++) {
            sum -= height[j];
            if (sum == 100) {
                find = 1;
                break;
            }
            sum += height[j];
        }
        if (find == 1)
            break;
        sum += height[i];
    }
    for (k = 0; k < 9; k++) {
        if (k != i && k != j)
            printf("%d\n", height[k]);
    }

    return 0;
}

풀이: 11분
코딩 + 디버깅: 9분

 

처음엔 재귀로 구현하려했는데 for문으로 간결하게 표현할 수 있어 for문을 선택했다.
중첩된 2번째 for문 들어가기 전에 sum의 값이 100보다 작으면 종료하는 문장을 넣을까 하다 반복 횟수가 적으니 넣지 않았다.
근데 생각해보니 sort를 한 뒤이므로 조건을 걸지 않아도 sum의 값이 100보다 작아지는 경우가 나오기 전에 답이 구해질 터였다.
그럼 저 조건이 필요 없어 보이지만 난쟁이가 9명이 아니라 10억명이고 찾는 난쟁이는 7명이면 sort를 출력 직전에 하는 것이 옳다.(이 경우엔 O(n^2)인 이 알고리즘을 사용하기 어렵겠지만...) 따라서 100보다 작으면 종료하는 조건이 연산량을 줄이는데 도움이 될 수 있다.