백준 2309번 일곱 난쟁이 문제를 풀어보았습니다.
이 문제는 아홉 명의 난쟁이 중에서, 키의 합이 정확히 100이 되는 일곱 명을 찾는 문제입니다.
문제 설명
백설공주와 함께 사는 일곱 난쟁이의 키 합은 100입니다.
그런데 아홉 명의 난쟁이 키가 주어졌을 때, 이 중 진짜 일곱 난쟁이를 찾아 오름차순으로 출력해야 합니다.
입력은 아홉 줄에 걸쳐 주어지고, 각 난쟁이의 키는 모두 다릅니다.
정답이 여러 개라면 아무거나 출력해도 됩니다.
처음 생각한 아이디어
핵심은 결국 아홉 명 중 두 명을 제외했을 때 남은 일곱 명의 합이 100이 되는 경우를 찾는 것입니다.
즉, 전체 합을 먼저 구해두고
아홉 명 중 두 명을 골라 빼서 100이 되는지를 확인하면 됩니다.
이 방식은 자연스럽게 조합을 떠올리게 합니다.
반대로 생각하면, 아홉 명 중 일곱 명을 직접 뽑아서 합이 100인지 확인하는 방식도 가능합니다.
이 경우는 순열/선택 기반 방식으로도 접근할 수 있습니다.
1. 조합을 사용한 풀이
먼저 전체 아홉 명의 키 합을 구해둡니다.
그 다음 아홉 명 중 두 명을 조합으로 선택해서, 그 둘을 뺐을 때 남은 합이 100이 되는 경우를 찾습니다.
이렇게 찾은 두 명은 가짜 난쟁이이므로, 이후 출력할 때 제외하면 됩니다.
코드
#include <bits/stdc++.h>
using namespace std;
int sum = 0;
vector<int> littleMan;
int liyer[2] = {0};
void getSum() {
for (int i = 0; i < 9; i++) {
sum += littleMan[i];
}
}
void Combination() {
for (int i = 0; i < 9; i++) {
for (int j = i + 1; j < 9; j++) {
int temp = sum;
temp -= littleMan[i];
temp -= littleMan[j];
if (temp == 100) {
liyer[0] = i;
liyer[1] = j;
}
}
}
}
int main() {
for (int i = 1; i <= 9; i++) {
int tmp;
cin >> tmp;
littleMan.push_back(tmp);
}
getSum();
sort(littleMan.begin(), littleMan.end());
Combination();
for (int i = 0; i < 9; i++) {
int flag = 0;
for (int j = 0; j < 2; j++) {
if (i == liyer[j]) {
flag = 1;
break;
}
}
if (flag) {
continue;
}
cout << littleMan[i] << endl;
}
return 0;
}풀이 흐름
- 아홉 명의 키 전체 합을 먼저 구한다.
- 난쟁이 배열을 오름차순 정렬한다.
- 아홉 명 중 두 명을 조합으로 선택해서 전체 합에서 빼본다.
- 결과가 100이면, 그 두 명의 인덱스를 저장한다.
- 마지막에 저장된 두 명을 제외하고 나머지를 출력한다.
이 방식은 문제의 핵심을 가장 직접적으로 반영한 풀이입니다.
전체 합을 이용하므로 불필요하게 일곱 명의 합을 계속 새로 구하지 않아도 된다는 점도 깔끔합니다.
2. 순열을 사용한 풀이
다른 방식으로는 아홉 명 중 일곱 명을 직접 선택해서, 그 일곱 명의 합이 100인지 확인하는 방법도 있습니다.
노션에서는 순열 방식으로 정리해두었습니다.
앞에서부터 일곱 명을 고르는 형태로 순서를 바꾸면서 확인하고, 합이 100이면 바로 출력 후 종료하는 구조입니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> littleMan;
vector<int> realMan;
void checkSum() {
int sum = 0;
for (int i = 0; i < 7; i++) {
sum += littleMan[i];
}
if (sum == 100) {
for (int i = 0; i < 7; i++) {
realMan.push_back(littleMan[i]);
}
sort(realMan.begin(), realMan.end());
for (int i = 0; i < 7; i++) {
cout << realMan[i] << "\n";
}
exit(0);
}
}
void makePermutation(int n, int r, int depth) {
if (depth == r) {
checkSum();
return;
}
for (int i = depth; i < n; i++) {
swap(littleMan[i], littleMan[depth]);
makePermutation(n, r, depth + 1);
swap(littleMan[i], littleMan[depth]);
}
}
int main() {
for (int i = 0; i < 9; i++) {
int temp;
cin >> temp;
littleMan.push_back(temp);
}
makePermutation(9, 7, 0);
}풀이 흐름
- 아홉 명 중 일곱 명을 선택하는 순열을 만든다.
- 앞의 일곱 명이 선택된 상태라고 보고 합을 계산한다.
- 합이 100이면 정답이므로 정렬 후 출력하고 종료한다.
이 방식도 충분히 문제를 해결할 수 있습니다.
어떤 방식이 더 괜찮았을까
노션에도 적어두었듯이, 개인적으로는 조합 방식이 더 좋은 풀이라고 생각했습니다.
이유는 다음과 같습니다.
- 문제 자체가 “아홉 명 중 두 명이 가짜”라는 형태로 주어져 있어서 접근이 자연스럽고
- 전체 합을 활용하면 로직이 더 단순해지며
- 구현도 순열 방식보다 조금 더 직관적입니다
물론 입력 크기가 작기 때문에 두 방식 모두 충분히 통과 가능한 풀이입니다.
그래서 이 문제는 단순히 정답을 맞히는 것보다,
같은 문제를 조합과 순열 두 관점으로 모두 바라볼 수 있다는 점이 더 의미 있었던 것 같습니다.
