[C언어] 백준 3040 : 백설 공주와 일곱 난쟁이

백준 3040 : 백설 공주와 일곱 난쟁이

 

문제 링크

www.acmicpc.net/problem/3040

3040번: 백설 공주와 일곱 난쟁이

 

 

문제 내용

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱 개, 접시 일곱 개, 나이프 일곱 개를 준비한다.

어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.

백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.

아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)

 

 

Idea

9명의 난쟁이중 7명의 난쟁이 숫자의 합이 100이다.

따라서, 총합에서 100을 빼면 남은 숫자는 두 명분의 합계이므로 이를 이용하여 문제를 풀이한다.

 

이중 for문을 사용하여 9명의 난쟁이 중 2명을 뽑는 모든 경우의 수를 탐색한다.

 

그리고 비슷한 문제로 2309번: 일곱 난쟁이 문제를 추천한다.

아래 코드에서 정렬 기능만 추가하면 되는 문제이다.

 

 

Code

#include <stdio.h>
 
int main() {
    int arr[9];
    int check[9] = { 0, };
    int sum = 0;
 
    //각 난쟁이의 숫자를 입력받고, 
    //총 합계를 구함.
    for (int i = 0; i < 9; i++) {
        scanf("%d", &arr[i]);
        sum += arr[i];
    }
 
    //총합에서 100만큼 빼주기
    sum -= 100;
 
    //두명의 합이 sum과 같은지 확인
    int find = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = i + 1; j < 9; j++) {
            //찾으면 해당 인덱스를 표시하고 종료
            if (arr[i] + arr[j] == sum) {
                check[i] = check[j] = 1;
                find = 1;
                break;
            }
        }
        if (find) break;
    }
 
    //결과출력
    for (int i = 0; i < 9; i++) {
        if (!check[i]) printf("%d\n", arr[i]);
    }
 
    return 0;
}