글 읽기 - 도와주세요 :(

kso4013 7년 전 0

반례가 무엇이 있는지 궁금하네요 ㅠㅠ

제가 구현한 점화식은

"자신을 포함 이후 경로에서 최대값을 도출해내기" 였습니다.

타 질문들을 보면서 대입을 해봤는데 값도 잘 나오는 것 같고..

반례나 조언! 부탁드립니다 ㅠ_ㅠ

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

using namespace std;

int tri(int idx, int num);

int cache[500][500], input[500][500];
int n;

int main(){
    memset(cache, -1, sizeof(cache));
    memset(input, -1, sizeof(input));
    
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<i+1;j++)
            cin>>input[i][j];
    
    tri(0,0);
    cout<<cache[0][0]<<endl;
    
    return 0;
}

int tri(int idx, int num){
    int& ret=cache[idx][num];
    int in=input[idx][num];
    
    if(ret!=-1)
        return ret;
    
    if(idx==n)
        return 0;
    
    return ret=max(tri(idx+1, num)+in, tri(idx+1, num+1)+in);
}

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

문제

문제

출처

ICPC

도와주세요 :(

kso4013 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말