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

◆ 문제 링크 : https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

 

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

 

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> key(9);	// 0으로 초기화되어 있음
int two_sum[9][9];	// 0으로 초기화되어 있음
int key_sum = 0;

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

	// 난쟁이의 키 하나씩 입력받으면서, 전체 난쟁이의 키의 합 초기화
	for (int i = 0; i < 9; i++) {
		cin >> key[i];
		key_sum += key[i];
	}

	// 두 난쟁이의 키의 합을 배열에 저장, key[i][j] = i번째 난쟁이와 j번째 난쟁이의 키의 합
	for (int i = 0; i < 9; i++) {
		for (int j = 1; j < 9; j++) {
			if (i >= j) continue;
			two_sum[i][j] = key[i] + key[j];

			if (key_sum - two_sum[i][j] == 100) {
				key.erase(key.begin() + j);	// j번째 난쟁이 키 제거
				key.erase(key.begin() + i);	// i번째 난쟁이 키 제거
				sort(key.begin(), key.end());	// 7명의 난쟁이 키 오름차순 정렬
				for (int i = 0; i < key.size(); i++) {
					cout << key[i] << "\n";
				}
				return 0;	// 정답 출력 후 프로그램 종료
			}
		}
	}
	return 0;
}

 

해설

- 9명의 난쟁이 중 7명의 키의 합이 100이므로, 7명의 키의 합을 직접 더해 100임을 알아내는 것보다, 9명 전체 키의 합에서 2명의 키를 뺐을 때 100이 됨을 이용해 문제를 해결하면 됩니다.

 

- 9명 전체의 키의 합을 저장할 변수 key_sum은 각 난쟁이의 키를 입력받으며 동시에 더해줍니다.

 

- 두 난쟁이의 키의 합을 저장하기 위해 key_sum이라는 이차원 배열을 선언했습니다. i, j번째 난쟁이의 키의 합은 j, i번째 난쟁이의 키의 합과 같으므로 굳이 두 번 계산하지 않기 위해 i < j인 상황만 고려했습니다. i와 j가 같은 경우는 그냥 한 명의 난쟁이의 키를 의미하는 것이기 때문에 계산하지 않았습니다.

 

- two_sum의 값을 저장하며 조건문을 이용해 9명 전체 키의 합에서 two_sum의 값을 뺐을 때 100이 되는 경우를 찾습니다. 문제에서 정답이 여러가지인 경우엔 아무거나 출력하라고 했기 때문에, 첫번째로 찾은 정답을 출력 후 바로 프로그램을 종료하고자 했습니다. 만약 가능한 정답이 여러가지인 경우 먼저 입력된 키를 제외한다 등의 특수 조건이 붙었을 경우엔 중간에 조건문으로 정답을 찾지 않고, two_sum배열을 완성한 후 정답을 구하면 됩니다.

 

- 찾은 두 명의 난쟁이 i, j번째 키를 제외하고 오름차순으로 출력합니다. 이 때 벡터의 특정 원소를 제외하는 erase를 사용했는데, erase를 사용할 경우 값이 지워짐과 동시에 인덱스 값이 조절됩니다. 즉 size가 9인 벡터에서 4번째 인덱스의 값을 erase할 경우 5번째 원소의 인덱스가 4로 바뀌며, 6번째는 5, 7번째는 6... 이런식으로 자동으로 인덱스 값이 조절된다는 것입니다. 따라서 정확하게 i, j번째 키를 제거하고 싶다면 i와 j중 큰 수인 j부터 erase 해줘야합니다. (위의 조건에서 i >= j인 경우에는 continue하고, i < j인 경우만 따졌기 때문입니다.) 혹시 i부터 erase해주고 싶다면 j가 아닌 j-1를 erase 해주어야 합니다.

 

- algorithm 헤더에 포함된 sort함수를 이용해 벡터를 오름차순으로 정렬 후 출력했습니다.