[Silver 2] 2961 도영이가 만든 맛있는 음식

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

2961번: 도영이가 만든 맛있는 음식

 

이 문제는 조합을 이용한 완전 탐색 문제이다.

 

조건에 따라 음식을 만들 수 있는 경우의 수는 {1}, {2}. {3}, {4}, {1,2}, {1,3}, {1,4}, ..., {1,2,3,4} 등이 존재한다.

따라서 입력으로 들어온 신맛과 쓴맛의 차이를 조합하여 최소 값을 구하면 해결할 수 있다.

 

최소 값을 구하는 과정은 다음과 같다.

1. 입력은 신맛과 쓴맛이 존재하기 때문에 pair형 배열을 사용해 입력 받는다.
2. 1번째인 경우부터 조합을 구한다.
   • 음식을 만들기 위해서는 최소 1개의 재료가 있어야하기 때문에 counter가 0보다 큰 경우에만 연산을 진행한다.
     • 연산을 진행하기 위해 box 배열에 존재하는 재료를 꺼낸다.
     • 먼저 0번째 인덱스에 있는 재료를 고른다. 이는 재료가 1개만 존재하는 경우가 있어 0번째 인덱스만 뽑은것
     • 재료가 더 존재한다면 신맛은 곱하고 쓴맛은 더하는 과정을 거친다.
     • 재료의 차이의 절대 값이 기존에 연산한 결과보다 작다면 갱신
   • 더이상 재료를 고를 수 없다면 조합을 멈춘다.
   • 조합 가능한 재료를 고른다.
     • counter 변수에 따라 배열에 재료를 갱신한다. 이는 counter가 0인 경우 0번째 인덱스에 0번째, 1번째, ... N 번째 재료가 들어갈 것이고, 다음 조합에 따라 계속해서 재료가 채워질 것이다.
     • 다음 재료를 고르거나 연산을 진행하기 위해 combination 함수를 호출한다.

 

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

int N;
pair<int, int> foods[11];
pair<int, int> box[11];
int result = 987654321;

void combination(int index, int counter) {
	if (counter > 0) {
		int S = box[0].first;
		int B = box[0].second;
		for (int i = 1; i < counter; i++) {
			S *= box[i].first;
			B += box[i].second;
		}
		result = min(result, abs(S - B));
	}
	if (counter == N) return;
	for (int i = index; i < N; i++) {
		box[counter] = { foods[i].first, foods[i].second };
		combination(i + 1, counter + 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) 
		cin >> foods[i].first >> foods[i].second;
	

	combination(0, 0);

	cout << result << '\n';
	return 0;
}