1932번-정수 삼각형

문제

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

접근방법

1) 접근 사고

배열이 주어지고 재귀함수를 y,x의 인덱스 값을 가지고 이동시키면서 비교연산을 통해 큰 값을 반환해주면 되는 문제였습니다.

저는 탑다운 형식으로 구현하였습니다.

 

2) 시간 복잡도

O(n)에 해결되는 문제였습니다.

 

3) 배운 점

배열에서 인덱스를 통한 이동값을 구하는 문제가 간혹 출제되는거 같은데 일종의 틀이 정해져 있는거 같아서 유형을 복습하기에 좋았습니다.

 

4) PS

비슷한 유형의 문제를 풀다가 const int max를 통한 배열값 지정시에 실수를 해서 오류를 찾느라 시간이 좀 걸렸습니다.

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 501;
int cache[MAX][MAX];
int board[MAX][MAX];
int n;
 
//y는 깊이 x는 열을 의미
int search(int y, int x)
{
    //범위 초과시 종료
    if(y >= n || x >= n)
        return 0;
 
    //끝 배열에 들어갈 경우 맨 밑줄의 값을 반환
    if(y == n - 1)
        return board[y][x];
 
    int &ret = cache[y][x];
 
    if(ret != -1)
        return ret;
 
    //밑에 값과 밑 우측 값 중 더하였을 때 더 큰 값을 반환한다
    ret= max(board[y][x] + search(y + 1, x), board[y][x] + search(y + 1, x + 1));
    return ret;
}
 
int main(void)
{
    fastio;
    cin >> n;
 
    memset(cache, -1 , sizeof cache);
 
    //직각 삼각형을 만들어준다.
    for(int i =0; i < n; i++)
        for(int j = 0; j <= i ; j++)
            cin >> board[i][j];
 
    cout << search(0,0) <<"\n";
}