글 읽기 - 시간을 어떻게 줄여야 할까요..

chso2 8년 전 0

시간을 어디서 더 줄여야할까요...

도저히 모르겠습니다.

#include <stdio.h>
#define max(a,b) a>b?a:b
 
/*
     2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열
     점수는 0보다 크거나 같고, 100보다 작거나 같은 정수
*/
int T;
int N;          //n (1 ≤ n ≤ 100,000)
int i;
int j;
int k;
int arr[2][100002];
int cnt = 0;
 
int compared(int a, int b){
    if (b >= N){
        return 0;
    }
    if (a == 0){
        cnt = max(compared(a + 1, b + 1),compared(a + 1, b + 2)) + arr[a][b];
    }else{
        cnt = max(compared(a - 1, b + 1),compared(a - 1, b + 2)) + arr[a][b];
    }
    return cnt;
}
 
int main(){
    scanf("%d", &T);
    for (i = 0; i < T; i++){
        scanf("%d", &N);
        for (j = 0; j < 2; j++){
            for (k = 0; k < N; k++){
                scanf("%d", &arr[j][k]);
            }
        }
        max(compared(0, 0), compared(1, 0));
        printf("%d", &cnt);
        cnt = 0;
    }
}

indioindio 8년 전 0

compared 의 인자를 출력해보시면 겹치는 경우가 많다는 것을 확인하실 수 있습니다.

메모이제이션에 대해서 검색해보세요.

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

문제

문제

출처

ICPC

시간을 어떻게 줄여야 할까요..

chso2 8년 전 0

indioindio 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말