문제 이해 단계
재료의 개수 N개가 주어지고 각 재료마다의 쓴맛과 단맛 정보가 주어진다.
쓴맛은 쓴맛끼리 곱연산을 하고 단맛은 단맛끼리 합연산을 해서
(총 쓴맛 - 총 단맛) 해서 최대한 절댓값이 작은 수를 구하는 문제.
문제 접근 단계
일단 문제 조건에서 봐야 할 점은 재료 N이 최대 10개까지만 있다는 점이다.
10개밖에 안되기 때문에 브루트포스가 가능하고, 시간적인 부담이 적다는 것을 알 수 있다.
우선 구해야 하는 것이 뭔지부터 살펴보자. 구하자고 하는 것은 연산의 결과인데,
크게 보면 N개의 재료 중에서 몇 가지를 골라서 그 안에 값을 계산하는 것이다.
여기서 중요한 점은 몇 가지라는 점, 1개가 될 수도 있고 2개가 될 수도 있고 전부가 될 수도 있는 것이다.
그래서 뭔가 공식을 세우거나, 재료들의 값을 비교해서 제외하는 방식을 쓰는 건 비효율적일 것 같았다.
차라리 재료가 10개밖에 안되기 때문에 가능한 모든 경우의 수 중 가장 절댓값이 낮은 수를 구하는 것이 낫다.
재료 하나의 관점에서 보면 결국 해당 재료가 포함 유무를 따지는 것이기 때문에
한 재료에서 다음 재료로 넘어갈 때 이 두 가지의 경우의 수를 나눠서 해주면 된다.
그림으로 나타내보면 간단하게 이렇게 된다.
재료가 3개(A, B, C)인 경우이다.
초록색 원은 포함된 경우이고, 주황색 원은 포함되지 않은 경우이다.
비슷한 그래프가 2개가 그려진 이유는
재료 A도 포함되지 않을 수 있기 때문에 이를 분리해 주기 위해서이다.
이렇게 모든 재료에 대해서 포함, 불포함에 대한 경우의 수에 대해 분리해줘야 한다.
단, 여기서 한 가지 경우의 수를 제외해줘야 하는데,
바로 오른쪽에 주황색 원으로만 이루어진 경우이다.
해당 경우는 아무런 재료도 사용하지 않는 경우이기 때문에,
문제에서 언급한 "적어도 한 가지 재료" 조건을 위배한다.
그래프가 저렇게 나타낼 수 있으면 자연스럽게 생각나는 게 재귀함수이다.
재귀함수를 통해 다음 재료를 포함하는 경우의 수와
포함하지 않는 경우의 수를 분리하여 호출하고,
또 그 함수가 포함하는 경우와 포함하지 않는 경우의 수를 호출하고...
하다가 끝까지 탐색을 마치면 모은 재료들에서 쓴맛과 단맛을 계산하여
절댓값이 가장 작은 것을 답으로 정한다.
이는 사실 N이 10밖에 되지 않기 때문에, 따로 방문처리나 메모라이징 기법이 필요 없을 것 같다.
문제 구현 단계
int N;
int ans = INT32_MAX; // 정답을 담을 전역변수
vector<vector<int>> stuff; // 재료 리스트
vector<int> solution(int idx, bool contain, vector<int> cnt){
//contain -> 다음 인덱스를 포함시킬지 말지 결정
if(idx >= N) {
vector<int> tmp(2);
// 재료가 0개인 경우
for(auto it : cnt) if(it == 0){
tmp[0] = INT32_MAX; // 쓴맛
tmp[1] = 0; // 단맛
return tmp;
}
return cnt;
}
// 해당 재료를 포함하는 경우
if(contain){
cnt[0] = cnt[0] * stuff[idx][0];
cnt[1] = cnt[1] + stuff[idx][1];
}
vector<int> case1 = solution(idx+1,true,cnt); // 포함하는 경우의 수 호출
vector<int> case2 = solution(idx+1,false,cnt); // 포함하지 않는 경우의 수 호출
int val1 = abs(case1[0] - case1[1]);
int val2 = abs(case2[0] - case2[1]);
// 두 경우의 수 중 절대값이 더 낮은 값을 선정
if(val1 < val2) {
ans = min(ans,val1);
cnt[0] = case1[0];
cnt[1] = case1[1];
}
else{
ans = min(ans,val2);
cnt[0] = case2[0];
cnt[1] = case2[1];
}
return cnt;
}재귀함수를 호출하는 solution 함수이다.
매개변수로 재료의 인덱스 번호와, 포함 여부, 그리고 현재 쓴맛과 단맛이 담긴 벡터가 주어진다.
일단 재귀함수를 호출하기 전에 당연히 재료 N개가 넘는지를 확인하는 절차가 필요하다.
이는 인덱스(Idx) 번호가 N과 같은지를 확인하는 것으로 하면 된다.
만약 같다면 이때까지 계산했던 cnt를 반환한다.
이때, 해당 값이 재료 0개(모든 경우의 수가 불포함)인지를 확인하기 위해
초기에 할당했던 값(0)이 남아 있는지를 확인한다.
있으면 그 값이 선택되지 않기 위해 단맛과 쓴맛의 차이를 크게 하여 절댓값을 크게 만든다.
그 아래부터는 위에서 언급한 것처럼 포함하는 경우의 수와 포함하지 않는 경우의 수를 분리하여 호출하고,
두 경우의 수 중 더 낮은 절댓값을 가지는 것을 결과로 가져온다.
늘 말했지만, 사실 재귀함수는 코드를 작성하고 설명하는 게 어렵지 코드는 짧다.
이상이 코드에 대한 설명이고 아래는 전체 코드를 올리고 설명을 마치겠다.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int N;
int ans = INT32_MAX; // 정수형 최대값
vector<vector<int>> stuff; // 재료 리스트
vector<int> solution(int idx, bool contain, vector<int> cnt){
//contain -> 다음 인덱스를 포함시킬지 말지 결정
if(idx >= N) {
vector<int> tmp(2);
// 재료가 0개인 경우
for(auto it : cnt) if(it == 0){
tmp[0] = INT32_MAX; // 쓴맛
tmp[1] = 0; // 단맛
return tmp;
}
return cnt;
}
// 해당 재료를 포함하는 경우
if(contain){
cnt[0] = cnt[0] * stuff[idx][0];
cnt[1] = cnt[1] + stuff[idx][1];
}
vector<int> case1 = solution(idx+1,true,cnt); // 포함하는 경우의 수 호출
vector<int> case2 = solution(idx+1,false,cnt); // 포함하지 않는 경우의 수 호출
int val1 = abs(case1[0] - case1[1]);
int val2 = abs(case2[0] - case2[1]);
// 두 경우의 수 중 절대값이 더 낮은 값을 선정
if(val1 < val2) {
ans = min(ans,val1);
cnt[0] = case1[0];
cnt[1] = case1[1];
}
else{
ans = min(ans,val2);
cnt[0] = case2[0];
cnt[1] = case2[1];
}
return cnt;
}
int main(){
scanf("%d",&N);
for(int i = 0; i < N; i++){
vector<int> tmp;
int sour, bitter;
scanf("%d %d",&sour,&bitter);
tmp.push_back(sour);
tmp.push_back(bitter);
stuff.push_back(tmp);
}
vector<int> tmp = {1,0};
vector<int> val1 = solution(0,true,tmp);
vector<int> val2 = solution(0,false,tmp);
printf("%d",ans);
}
시행착오
어떻게 풀어야 할지 아이디어는 바로 알았는데, 이상하게 구현이 안 됐다.
정확히는 구현을 했는데 계속 이상하게 나와서 방법을 자꾸만 바꿔서 오래 걸렸다.
이는 그냥 내가 프로그래밍 능력 부족이라고 생각하고 반성하고 있다.
나는 이 문제를 그냥 재귀로 풀었는데, 풀고 나서 태그를 보니까 비트마스킹, 백트래킹 등 다양한 방법이 있던데
비트마스킹으로 풀면 간단할 거 같긴 한데..
비트마스킹.. 음.. 예.. 한번 해보긴 해야 할 거 같은데 손이 잘 안 간다.