TRIANGLEPATH

  • istien
    istien

    TRIANGLEPATH
    이 문제에서 어느 것이 문제 일까요...
    book 홈페이지에 있는 소스코드로 제출을 하여도 오답 처리가 되네요

    #include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;

int cache[101][101];
int board[101][101];
int size;


int tri_sum(int y,int x,int sum) 
{
    if(y == size-1)
        return sum+board[y][x];
    int &ret = cache[y][x];
    if(cache[y][x] != -1)
        return ret;
    sum += board[y][x];
    ret = max(tri_sum(y+1,x,sum),tri_sum(y+1,x+1,sum));
    return ret;

}

int main()
{
    int TestCase=0;
    cin>>TestCase;
    assert(TestCase<=50);
    while(TestCase--)
    {
        cin>>size;
        assert(2 <= size && size <= 100);
        for(int i = 0 ; i < size ; i++)
        {
            for(int j = 0 ; j < i+1 ; j++)
            {
                cache[i][j] = -1;
                cin>>board[i][j];
            }
        }

        cout<<tri_sum(0,0,0)<<endl;
    }
}

    9년 전
4개의 댓글이 있습니다.
  • istien
    istien

    https://algospot.com/judge/problem/read/TRIANGLEPATH


    9년 전 link
  • istien
    istien

    예제 통과는 되었는데.. 혹시 반례라도 알려주신다면 감사하겠습니다


    9년 전 link
  • JongMan
    JongMan

    홈페이지 코드에는 최대합을 반환하는 함수, 최대경로의 개수를 반환하는 함수 등이 있는데 최대 경로의 개수를 출력하도록 제출하셔서 틀린 것이고요.

    이 코드에서는 메모이제이션이 잘못되었습니다. y, x가 같더라도 sum이 다르다면 결과값이 서로 달라지게 됩니다. y, x가 같다면 항상 결과값이 같도록 tri_sum 함수의 정의를 바꾸셔야 합니다.


    9년 전 link
  • istien
    istien

    감사합니다 ^^


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.