[백준 알고리즘] 3040번: 백설 공주와 일곱 난쟁이
May 05, 2020
3040번: 백설 공주와 일곱 난쟁이
문제
매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.
어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.
백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.
아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)
입력
총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.
출력
일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.접근 방법:
처음에는 이것저것 이상하게 시도를 많이 해봤는데 잘 안돼서 단순하지만 확실한 방법으로 해결했다. 벡터에 입력을 모두 저장하고 모든 요소들을 이중 for 문으로 순회하면서 두 개의 요소의 값을 0으로 만든다. 어차피 입력은 1이상 99이하이므로 0이 들어올 일이 없어 괜찮다. 그리고 벡터의 요소들의 합을 구해 100인지 확인한다. 100이라면 0을 제외한 벡터 요소를 출력하고 프로그램을 종료한다. 0으로 만들었던 값은 다음 검사를 위해서 복구해줘야 하는데 임시로 기억시키기 보다는 그냥 새로운 벡터를 하나 만들어서 한 검사가 새로 시작될 때마다 기존 입력으로 받았던 벡터를 assign을 통해 복사해두고 검사를 진행했다.
통과 코드:
#include <cstdio>
#include <vector>
using namespace std;
int main(){
vector<int> dwarves;
// 입력 받기 //
for (int i = 0 ; i < 9 ; i++){
int dwarf;
scanf("%d", &dwarf);
dwarves.push_back(dwarf);
}
int sum = 0;
vector <int> result;
for (int i = 0 ; i < 8 ; i++){
for (int j = i+1 ; j < 9 ; j++){
result.assign(dwarves.begin(), dwarves.end()); // 새로운 벡터 만들고 난쟁이 목록을 복사
sum = 0; result[i] = 0 ; result[j] = 0; // i 와 j 번째 난쟁이를 0으로 만든다. 어차피 입력은 1이상으로 들어오기 때문에 상관없음
for(int dw : result){
sum += dw; // 난쟁이 더하기
}
if (sum == 100){ // 100이 되면 0으로 만든 난쟁이들만 없애고 출력해준다.
for(int dw : result){
if (dw == 0) continue;
printf("%d\n", dw);
}
return 0;
}
}
}
return 0;
}
