글 읽기 - 시간 초과

hasyhasy2001 1년 전 0

시간초과의 원인을 모르겠습니다. 다른 dp 문제들은 재귀로 했을 때 시간초과가 나지 않았는데

이 문제에서 나서 이유가 궁금합니다 .

#include <iostream>
#include <cstdio>

using namespace std;

int arr[100001][2]={0};
int save[100001][2]={0};

int f(int x,int y){
  if(x==1||x==0)
    return arr[x][y];
  if(save[x][y]!=0)
    return save[x][y];
  save[x][y]=max(f(x-1,1-y),f(x-2,1-y))+arr[x][y];
  return save[x][y];
  
}

int main() {
  int T,n;
  scanf("%d",&T);
  
  for(int i=0;i<T;i++){
    scanf("%d",&n);
    for(int j=1;j<n+1;j++){ //위에 줄 받으며 dp가 저장될 곳 초기화
      scanf("%d",&arr[j][0]);
      save[j][0]=0;
      
    }
    for(int j=1;j<n+1;j++){ //아래 줄 받으며 저장될 곳 초기화 
      scanf("%d",&arr[j][1]);
      save[j][1]=0;
    }
    
    int ans=max(f(n,0),f(n,1)); // 둘 중에 하나는 무조건 때야 하기 때문에 

    printf("%d\n",ans);
    
    
  }
  
  
}

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

문제

문제

출처

ICPC

시간 초과

hasyhasy2001 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말