[BOJ/백준 2309][C++] 일곱 난쟁이

문제

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

 

문제 내용

9명의 키가 주어지고, 이들 중 2명을 제외하여 키의 합을 100으로 맞추는 문제이다.

 

문제 풀이

전형적인 완전 탐색 문제이다.

일단 입력받은 키들의 합을 구하고, 이중 for문을 돌며 두 명을 골라 제외시키며 키의 합이 100이 되는지 아닌지를 확인하면 된다.
만약 키의 합이 100이 되면, 나머지 수들을 바로 출력해주고 프로그램을 종료하면 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <numeric> //accumulate() 들어있다.

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int arr[9];
	int sum = 0;
	for (int i = 0; i < 9; i++) cin >> arr[i];


	//문제 해결

	// 첫번째 인자는 시작지점 = 배열의 포인터
	// 두번째 인자는 끝나는지점 + 1 = a(배열의 포인터) + 배열의 크기
	sort(arr, arr + 9);
	
	//배열 시작 주소, 배열 끝 주소, 초기값
	sum = accumulate(arr, arr + 9, sum); 

	for (int i = 0; i < 8; i++) {
		for (int j = i; j < 9; j++) {
			if (sum - (arr[i] + arr[j]) == 100) {
				
				//결과 출력
				for (int k = 0; k < 9; k++) {
					if (k == i || k == j) continue;
					else cout << arr[k] << '\n';
				}
				return 0;
			}
		}
	}

}

 

문제 코드 설명

1) 문제 해결

일단 배열을 정렬하기 위해 sort() 함수를 사용한다.
(일곱 난쟁이의 키를 오름차순으로 출력하기 위함)

이후 배열에 담긴 값들을 모두 합한다.
이를 위해 accumulate() 함수를 사용하였으며 numeric 헤더 안에 들어있다.

위 과정이 모두 끝나면, 이중 for문을 돌며 키의 합을 100으로 만들기 위해 제외할 2명을 고르면 된다.