[백준] 도영이가 만든 맛있는 음식(2961)

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

문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

 

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

 

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

 

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

풀이

재귀함수를 이용해서 풀 수 있는 문제이다.

주어진 N의 범위가 10이므로, N개 중 1~N개를 종류마다 뽑는 경우의 수는 nC1 + nC2 + nC3 + … + nCn으로 2^n -1 의 개수가 나온다. 따라서, N이 최대 10인경우, 1023가지의 경우의 수가 나오는 셈이다.

 

그럼 재귀로 시간초과없이 풀 수 있다는 소리. 이때, 재귀 과정에서 중복된 경우의 수를 제외해야 함을 주의하도록 한다.
(예> 1234, 2134는 같은 경우의 수로 판단)

C++ 소스코드

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int N, x, y, ans= 2e9;

struct flavor
{
    int x, y;
};

flavor arr[11];
bool used[11];

void findAns(int cnt, int idx, int mul, int sum) {
    if (cnt >= 1) {
        int result = abs(mul - sum);
        ans = ans > result ? result : ans;
    }

    for (int i = idx; i <= N; i++) {
        if (used[i] == false) {
            used[i] = true;
            findAns(cnt + 1, i, mul*arr[i].x, sum+arr[i].y);
            used[i] = false;
        }
    }
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &x, &y);
        arr[i].x = x;
        arr[i].y = y;
    }
    findAns(0, 1, 1, 0);
    printf("%d", ans);
    return 0;
}

부족한 부분

재귀함수는 아직도 어렵나보다.. 처음에는 무작정 배열의 첫번째 인덱스부터 탐색하게끔 하다보니, 중복되는 경우가 발생하여 시간초과가 났었다.

중복부분을 없애기 위해 재귀함수에 index라는 파라미터를 추가하여 탐색의 시작 위치를 지정하여 중복을 해결하였다.
아직 재귀함수를 내 마음대로 짜는데 어려움이 있는 듯 하다. 재귀 관련 문제를 많이 풀어보자..