[S2] 백준 2961번 도영이가 만든 맛있는 음식 C++ 백트래킹

리뷰

 

조합할 수 있는 모든 음식의 조합을 탐색하여 신맛과 쓴맛의 차를 구하는 문제

처음엔 모든 재료의 입력값이 10억 미만으로 봐서 어떻게 풀어야할지 정말 막막했다.

모든 재료를 사용해서 요리를 만들었을 때 10억 미만인 점을 꼭 읽길 바란다 ㅠㅠ

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

 

전역 변수

• n, ans : 재료의 개수를 저장할 변수n, 정답을 저장할 변수 ans 10억 이상으로 초깃값을 세팅해 준다.
• v, ing1, ing2 : 방문 배열v, 신맛과 쓴맛 재료를 저장할 배열 ing1, ing2 모두 재료의 최대크기 10으로 크기를 세팅한다.

 

함수

1. bt

void bt(int level, int val1, int val2)

 

백트래킹을 통해 완성된 음식의 쓴맛과 신맛의 차를 구하는 함수

1. level : 현재 재귀 단계
2. val1 : 신맛 재료의 누적 곱
3. val2 : 쓴맛 재료의 누적 합
4. 재귀 단계가 0이 아닐 경우 val2 - val1의 절댓값을 ans와 비교하여 최소값을 갱신해 준다.
5. 재귀 단계가 n에 도달했을 경우 리턴 처리해준다.
6. n번의 for문을 개행하여 이미 포함한 재료라면 continue 처리해 준다.
7. 사용하지 않은 재료라면 방문처리를 하고 val1, val2를 갱신 하고 재귀단계를 올려 탐색을 진행한다.
8. 재귀가 완료되었을 경우 방문 처리를 해제해 준다.

 

문제풀이

1. n값을 입력 받고 n번의 for문을 개행해 준다.
2. 각 입력값을 신맛 배열 ing1, 쓴맛 배열 ing2에 순서대로 저장해 준다.
3. bt함수를 통해 탐색을 진행한다 level = 0, val1 = 1, val2 = 0이 초깃값이다.
4. 탐색을 마친 후 ans에 저장된 값을 출력해 준다.

 

참고 사항

• 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들어야 한다.
• 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.
• 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.
• 기저조건에 달했을때가 아니라 재귀단계가 1이상이면 각 재귀단계마다 ans값을 최신화 해주어야 한다.

 

정답 코드

#include<iostream>

using namespace std;
int n, ans = 1e9;
int v[10], ing1[10], ing2[10];

void bt(int level, int val1, int val2) {
	if (level) ans = min(ans, abs(val2 - val1));
	if (level == n) return;	

	for (int i = 0; i < n; i++) {
		if (v[i]) continue;
		v[i] = 1;
		bt(level + 1, val1 * ing1[i], val2 + ing2[i]);
		v[i] = 0;
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> ing1[i];
		cin >> ing2[i];
	}
	bt(0, 1, 0);
	cout << ans;
}