[ALGOSPOT] TRIANGLEPATH

algospot.com/judge/problem/read/TRIANGLEPATH

algospot.com :: TRIANGLEPATH

 

<아이디어>

밑으로 1층씩 내려가면서 바로 밑 자리 최대값 갱신, 오른쪽 아래 최대값 갱신으로 저장.

 

<구현>

아이디어 그대로 구현(?) 하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc; cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        vector<vector<int>> v(n, vector<int> (n)), dp(n, vector<int> (n, 0));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
                cin>>v[i][j];
        }
        dp[0][0] = v[0][0];
        for(int i=0;i<n-1;i++)
        {
            for(int j=0;j<=i;j++)
            {
                dp[i+1][j] = max(dp[i+1][j], dp[i][j]+v[i+1][j]);
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+v[i+1][j+1]);
            }
        }
        int mx = dp[n-1][0];
        for(int i=0;i<n;i++)
            mx = max(mx, dp[n-1][i]);
        cout<<mx<<endl;
    }
    return 0;
}

 

다음 소스코드는 책을 보고 참고한 코드입니다.

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int n, triangle[101][101];
int cache[101][101];
 
int path(int y, int x)
{
    if(y==n-1) return triangle[y][x];
    int& ret = cache[y][x];
    if(ret!=0) return ret;
    return ret = max(path(y+1, x+1), path(y+1, x))+triangle[y][x];
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
                cin>>triangle[i][j];
        }
        cout<<path(0, 0)<<endl;
    }
    return 0;
}