[백준 BOJ] 3040번 백설 공주와 일곱 난쟁이 (C++/cpp)

문제 설명

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

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

 

접근 방법 - 브루트포스 알고리즘의 기본 문제

백준의 3040번 문제는 브루트포스 알고리즘을 활용하여 해결해야 하는 기본 문제이다.

해당 문제는, 아홉 난쟁이의 모자에 적힌 숫자들을 통해 이들 중 일곱 난쟁이를 추려내야 하는 문제이다.

여기서, 일곱 난쟁이 모자의 숫자들을 합하면 100이 된다는 점을 이용하여 일곱 난쟁이를 추려내려 한다.

필자의 경우엔, 아홉 난쟁이 모자의 숫자를 모두 더한 값에 특정 두 난쟁이 모자의 숫자들을  빼가면서 추측하였다.

바로 여기에서 이중 반복문을 활용한 브루트포스 알고리즘이 사용되는 것이다.

이 알고리즘을 어떻게 활용하였는지에 대한 설명은 아래에서 자세히 하고자 한다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 아홉 난쟁이 모자의 숫자들을 저장할 배열(a)을 선언한다. 뒤이어, 이들의 합을 저장할 변수 sum을 0으로 초기화하여 선언한다.

 

2) 반복문을 통해 숫자들을 입력받는다. 동시에 이들의 값을 sum에 더하도록 한다.

 

3) 이중 반복문을 통해, 임의로 두 난쟁이를 지목하도록 한다.

만일 지목된 두 난쟁이 모자의 숫자들을 sum에서 뺀 값이 100일 경우, 이 두 난쟁이는 일곱 난쟁이에 속하지 않는다.

따라서, 이들을 제외한 난쟁이 모자의 숫자를 순차적으로 출력하도록 한다.

 

4) 만일 3)에서 일곱 난쟁이 모자의 숫자들을 모두 출력하였다면, 즉시 실행 종료하도록 한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 3040번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int a[9];
	int sum = 0;
	for (int i = 0; i < 9; i++) {
		cin >> a[i];
		sum += a[i];
	}

	int i, j;
	for (i = 0; i < 8; i++) {
		for (j = i + 1; j < 9; j++) {
			if (sum - a[i] - a[j] == 100) {
				for (int k = 0; k < 9; k++) {
					if (k == i || k == j) { continue; }
					cout << a[k] << endl;
				}
				return 0;
			}
		}
	}
}

 

제출 결과

(2022.06.06 백준 3040번 문제 제출 결과)