글 읽기 - 재귀로 코드 작성했는데 시간초과가 뜨네요 ㅠㅠ

zmfldlwl 1년 전 0

최대한 시간 줄엿다고 줄엿는데도 이 문제 재귀로는 안되는 문제인가요?

											#include <iostream>
#include <memory.h>

using namespace std;

int n, m;
int arr[100];
int res;
bool flag = true;

void REQ(int loc, int num)
{
    arr[loc] = num;
 
    if (num > m)
        return;
    
    if (loc == n - 1)
    {
        res++;
        /*
        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
        */
        return;
    }

    for (int i = num*2; i <= m; i++)
    {
        if (flag)
        {
            int t = i;
            for (int j = 0; j < n - (loc + 1) - 1; j++)
            {
                t *= 2;
            }

            //true이면 시작점으로 가능하다
            if (t <= m)
            {
                //시작위치, 숫자
                REQ(loc + 1, i);
            }
            else
            {
                //이제 이 시작점 이후로는 시작위치가 불가능하기 때문에
                flag = false;
                return;
            }
        }
        else
            break;
    }
}

int main()
{
    int testcase;
    cin >> testcase;

    for (int test = 0; test < testcase; test++)
    {
        memset(arr, 0, sizeof(arr));
        res = 0;
        flag = true;

        cin >> n >> m;

        for (int i = 1; i <= m; i++)
        {
            int t = i;
            flag = true;

            for (int j = 0; j < n - 1; j++)
            {
                t *= 2;
            }

            //true이면 시작점으로 가능하다
            if (t <= m)
            {
                //시작위치, 숫자
                REQ(0, i);
            }
            else
            {
                //이제 이 시작점 이후로는 시작위치가 불가능하기 때문에
                break;
            }
        }

        cout << res << endl;
    }

    return 0;	/* 반드시 return 0으로 해주셔야합니다. */

}
										

ntopia 1년 전 0

구현하신 소스를 기준으로 설명을 드리자면

REQ(0, 1) 을 계산할 때 루프 안에서 언젠가는 REQ(1, 4) 를 부르겠죠?

마찬가지로 REQ(0, 2) 를 계산할 때도 루프 안에서 언젠가는 REQ(1, 4) 를 부르겠죠?

근데 REQ(0, 1) 안에서 REQ(1, 4) 를 부르나, REQ(0, 2) 안에서 REQ(1, 4) 를 부르나

REQ(1, 4) 가 계산해내는 값은 같을 것입니다.

근데 같은 걸 엄청나게 여러번 계산하겠죠? 그래서 시간초과가 납니다.

이 부분을 어떻게 하면 줄일 수 있을지...가 포인트 입니다.

zmfldlwl 1년 전 0

댓글달아주신 내용으로 생각해보면 이 문제는 재귀로는 답이 없는 문제가 맞나요? DP로 풀이해야 되는문제라고 말씀하시는거로 이해되서요.

ntopia 1년 전 0

DP를 재귀함수로 구현하는 테크닉도 있기 때문에 제가 아무 말도 안한거였어요..ㅋㅋ

보통 이걸 memoization 이라고 합니다.

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

문제

문제

출처

ACM-ICPC

재귀로 코드 작성했는데 시간초과가 뜨네요 ㅠㅠ

zmfldlwl 1년 전 0

ntopia 1년 전 0

zmfldlwl 1년 전 0

ntopia 1년 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

앱