글 읽기 - 시간초과 질문드립니다.

hwa3060 2년 전 0

보통 두 탑의 높이차로 문제를 해결하던데 이때 재귀함수에서 왼쪽탑과 오른쪽 탑의 높이를 받아 높이차를 계산하는 방식으로 풀었더니 시간초과가 났습니다. 높이차만을 이용해 푸는 것과 차이점이 무엇인지 모르겠습니다.

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int cache[500001][50];
int n;
vector<int> arr;

int func(int pos, int left, int right)
{
    if(abs(left-right) > 500000 / 2) return -1;
    if(pos >= n)
    {
        if(left == right) return left;
        else return -1;
    }

    int sub = abs(left - right);
    int& ret = cache[sub][pos];
    if(ret != -1) return ret;

    
    int res = max(max(func(pos+1, left + arr[pos],right),func(pos+1,left,right + arr[pos])),func(pos+1,left,right));
    return res;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    memset(cache, -1, sizeof cache);

    for(int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
        arr.push_back(a);
    }

    int ret = func(0,0,0);

    if(ret == 0)
        cout << -1 << "\n";
    else 
        cout << ret << "\n";

}

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

hwa3060 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말