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

문제 접근법.

- 모든 요리의 조합을 체크해야 한다.

- 특정 요리 조합마다 연산을 하는 것은 시간 초과가 발생한다.

- 이전 조합의 결과값을 이용해서 연산을 빠르게 하고 싶다.

 

코드 해설(C++).

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
 
int check[11] = { 0 };
 
int N;
long long sb[11][2];
long long t_s = 1, t_b = 0;
int answer = 0;
 
void recur(int n, int s, int b) {
    if (n == 0)
        return;
    
    if (abs(s - b) < answer)
        answer = abs(s - b);
 
    for (int i = 1; i <= N; i++) {
        if (check[i] == 0) {
            check[i] = 1;
            recur(n - 1, s / sb[i][0], b - sb[i][1]);
            check[i] = 0;
        }
    }
}
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> N;
    memset(check, 0, sizeof(check));
    for (int i = 1; i <= N; i++) {
        cin >> sb[i][0] >> sb[i][1];
        t_s *= sb[i][0];
        t_b += sb[i][1];
    }
 
    answer = abs(t_s - t_b);
    recur(N, t_s, t_b);
 
    cout << answer << endl;
    return 0;
}

 하향식 접근으로 재귀함수를 호출해야 한다. 입출력을 받으면서 모든 메뉴를 포함했을 때의 값을 저장한다.

이제, 재귀 함수를 호출해야 한다. 

 

 

 정의하는 재귀 함수는 '모든 메뉴가 포함된 상태에서 시작해서 모든 조합을 탐색하고 돌아오는 함수'이다.

1. 재귀 함수를 탈출하기 위한 조건, n = 0으로 설정한다.

2. 최솟값을 갱신하기 위한 if 코드를 설정한다. 

3. 체크 배열은 특정 메뉴가 제거되었음을 확인할 수 있는 장치이다.

 

 

 이 세가지만으로 함수를 작성했다. 재귀 함수를 머릿속으로 과정을 따라갈려면 복잡하다. 그래서, 재귀 함수는 정의하는 것이 가장 중요하며 정의가 올바른 논리 구조가 될 수 있도록 작성해야 한다. 재귀 함수가 익숙하지 않는 사람들은, 기초적인 재귀 문제(피보나치 수열, 하노이의 탑)을 익숙해지는 것을 추천한다.