[2309] 일곱 난쟁이

문제

2309번: 일곱 난쟁이

 

 

해결 방법

엄청 간단할 줄 알고 시작한건데 하루만에 끝내지 못했던 문제다.

내가 원래 생각한 방법은 어차피 결과를 오름차순으로 출력해야 한다면,

애초부터 9명의 몸무게를 오름차순으로 정렬한 후에 1번~7번 난쟁이의 몸무게 합이 100이라면 그 몸무게들을 출력하고,

100보다 작다면 8번 난쟁이 몸무게를 더한 후에 7번부터 1번까지 몸무게를 한번씩 빼보고 100이 된다면 출력 

뭐 이런식으로 생각했었는데 저 방법도 틀리진 않았다. 

하지만 7번에서 1번까지의 몸무게를 한번씩 빼보고, 초기화하고, 이 과정을 코드로 짜는게 너무 복잡할 것 같아서

결국 구글링의 도움을 조금 받았다. 근데 뭐 그냥 수학적으로 조금만 더 간단하게 생각했으면 되는 문제였다.

 

9명의 무게를 다 더한 후, 조합 가능한 모든 2명 몸무게 합을 생각하고 전체 합에서 빼서 100이 되면 종료하는 방식.

+ 버블소트로 마지막 정렬

 

브루트 포스(Bruth force)알고리즘을 사용하면 되는 문제였는데

브루트 포스 알고리즘이란, 조합 가능한 모든 경우를 하나씩 대입해 보는 방식으로 결국 노가다이다. 

 

무식한 방법같아 보이고 이게 무슨 알고리즘이라고 이름까지 붙여줬지? 했는데 항상 정확도 100%를 보장한다는 점에서

자원만 충분하다면 가장 강력한 방법이라고 한다. 

 

 

내 코드(C)

/*[2309] 일곱 난쟁이*/
/*sum of 9 dwarfs -(sum of some two dwarfs) = 100*/
/*brute force algorithm : method of substituting all possible combinations one by one*/
/*https://www.acmicpc.net/problem/2309*/
#include <stdio.h>

int main(void)
{
    int temp, flag = 1;
    int height[9], sum = 0;
    
    for (int i = 0; i < 9; i++) {
        scanf("%d", &height[i]);
        sum = sum + height[i];
    }
    
    for (int i = 0; i < 9; i++) {
        for (int j = i + 1; j < 9; j++) {
            if (sum - (height[i] + height[j]) == 100) {
                height[i] = 0;
                height[j] = 0;
                flag = 0; 
            }
        }
        
        if (!flag)
            break;
    }
	
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8 - i; j++) {
            if (height[j] > height[j + 1]) {
                temp = height[j];
                height[j] = height[j + 1];
                height[j + 1] = temp;
            }
        }
    }

    for (int i = 2; i < 9; i++) 
        printf("%d\n", height[i]);
}