글 읽기 - 직접 계산하여 값만 재귀함수로 넘길경우 에러 발생..?

desister 1년 전 0

하기와 같이 dfs 함수 내에서 res 값을 직접 계산하여 res 만 넘겨줄 경우 오답이 나오는데요..

res 값을 직접 계산하여 넘겨주는 경우하고 계산식 자체를 넘겨주는 경우 차이가 어떻게 되어서 결과가 달라지는건가요?

#include <iostream>
using namespace std;

int N; 
int maxvalue = -987654321;
int minvalue = 987654321;
int num[11];
int operator_[4]; // +, -, x, / 

int cal(int val, int n, int oper)
{
    if (oper == 0) return val + n;
    else if (oper == 1) return val - n;
    else if (oper == 2) return val * n;
    else if (oper == 3)
    {
        if (val < 0)
        {
            val = -val;
            return -(val / n);
        }
        else return val / n;
    }
    return -1; 
}

void dfs(int res, int n)
{
    if (n == N)
    {
        if (res > maxvalue) maxvalue = res;
        if (res < minvalue) minvalue = res; 
    }

    for (int j = 0; j < 4; j++)
    {
        if (operator_[j] > 0)
        {
            //res = cal(res, num[n], j);       여기서 직접 계산하여 dfs 에 res 값을 넘겨줄 경우 Fail 
            operator_[j]--;
            dfs(cal(res,num[n],j), n + 1);  // res 계산식을 직접 넘겨줌 
            operator_[j]++;
        }
    }
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++) cin >> num[i];

    for (int i = 0; i < 4; i++) cin >> operator_[i];

    dfs(num[0], 1);

    cout << maxvalue << endl;
    cout << minvalue << endl;
}

이유를 알아냈습니다..

res = cal(res, num[n], j) 를 쓰게 되면 맨 처음에 j = 0 일때의 res 값이 함수 내에서 계산되고,
계산된 res 와 n+1 을 넘기며 dfs 재귀함수가 돌아가게 됩니다.
이 때 재귀함수가 끝나게 되면 다시 원래 n 이 있던 처음 dfs 로 돌아오면서 j = 1 부터 다시
for문이 돌게 되는데 이 때 맨 처음에 함수가 받았던 res 값을 쓰는게 아니라 처음에 j = 0 일때
계산했던 res 값을 다시 쓰게 되면서 값이 오류가 나는 거네요...

따라서 res 값은 무조건 함수에서 처음 인자로 받은 void dfs (int res, int n) 일 때의 res 값을
무조건 유지해야 하고 다음 재귀함수로 넘길때는 함수내에서 계산이 아닌 계산식을 넘겨야만
기존 함수 res 값은 유지 -> 다음 재귀함수로의 값은 업데이트를 하면서 진행하게 되는 거네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

직접 계산하여 값만 재귀함수로 넘길경우 에러 발생..?

desister 1년 전 0

desister 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말