[백준 알고리즘][완전탐색] 2309번 일곱 난쟁이

문제 정의

총 9명 난장이들의 키가 주어지면 이들의 합이 100이 되는 일곱명의 난장이를 찾는 문제이다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/2309)

문제 풀이

입력되는 수는 항상 9개의 숫자이다. 이 숫자들의 합으로 100을 만들 수 있으면 탐색이 끝난다. N이 작기때문에 모든 경우를 다 계산해보는 완전탐색으로도 해결할 수 있는 문제이다. 9개의 숫자 중 7개의 숫자를 골라서 계산을 해보아야한다. 9개의 숫자 중에서 7개의 숫자를 어떻게 고를지 생각을 해봐야 한다.

사실 첫번째 생각부터 막혀서 9명 중에 어떻게 7명을 고르지 생각하다가 푼 사람의 리뷰를 봤는데 틀린 사람을 제거하면 되니까 9명 중에 제거를 할 2명을 고르면 된다. 9명 중에서 2명을 고르는 조합을 만들면 된다. 1~9번까지 있다면 차례대로 첫번째 제거할 사람으로 지목한 후, 한 사람에 대해서 나머지 한명씩을 붙여 조합을 만들면 된다. 그리고 처음엔 2명을 고른 다음, 나머지 7명을 전부 더해야한다 생각했는데 처음 입력이 들어왔을 때 키를 전부 더한다음 2명을 골랐을 때 그 2명의 키를 빼주면 되겠다.

*힌트를 참고하긴 했지만 한번에 맞았다!

코드

for(i=0; i<9; i++)

{

for(j=0; j<9; j++)

{

if(j != i){

result = totalNum-input[i]-input[j];

if(result == 100)

{

input[i] = -1;

input[j] = -1;

break;

}

}

}

if(result == 100)

break;

}

for (i = 0; i < 9; i++) {

        for (j = 0; j < 9 - i - 1; j++) {

            if(input[j] > input[j+1]) {

                tmp = input[j];

                input[j] = input[j+1];

                input[j+1] = tmp;

}

}

}

for(i=2; i<9; i++)

printf("%d\n", input[i]);