글 읽기 - 시간 초과가 왜 날까요??

akdlzmf6979 2년 전 0

O(n)이라고 생각했는데 시간 초과가 날만한 부분이 어떤 것인지 감이 오질 않네요... 고수님들 도와주십쇼~~

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int len, cache[2][100000], score[2][100001];

int maxSum(int y, int x)
//y,x 아래 그리고 우측으로 뗄 수 있는 스티커만 존재할 때 y, x에서의 점수 합의 최대값을 구하는 함수
//메모이제이션 활용
{
	if(x >= len) return 0;
	int ret = cache[y][x];
	if(ret != -1) return ret;
	
	if(y == 0)
		return ret = max(score[y][x] + maxSum(1, x + 1), maxSum(1, x));	
	else
	{
		if(x + 1 >= len)
			score[0][x + 1] = 0;
		ret = max(score[y][x] + score[0][x + 1] + maxSum(1, x + 2), 
									score[y][x] + maxSum(0, x + 2));
		return ret = max(ret, maxSum(0, x + 1));
	}
}

int main()
{
	int t;
	cin>>t;
	
	while(t--)
	{
		cin>>len;
		memset(cache[0], -1, sizeof(int) * len);
		memset(cache[1], -1, sizeof(int) * len);
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < len; j++)
				scanf("%d", &score[i][j]);
		cout<<maxSum(0, 0)<<endl;
	}		
}