백준(BOJ) 1932번 정수 삼각형

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

나의풀이 :

삼각형을 왼쪽으로 다 붙여서 직각삼각형으로 시작하자.

y = 0 , x =0 에서 출발하여 바로 아래 ( y= 1, x =0 ) 과 대각선 ( y =1 , x =1 ) 로 나아 갈 수 있게끔 재귀함수를 호출해준다.

n이 500이니 하나의 시작에서 갈 경우의 수는 2가지 임으로  2 ^ (500-1) 승의 경우의수가 나오고 완전 탐색으로는 접근이 불가능하다. 

동적 계획법을 통해 중복을 없애주자.

코드 ( C++ )

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

int N;

const int MAX = 500 + 1;

int triangle[MAX][MAX];

int cache[MAX][MAX];

int solve(int y, int x)

{

if (y ==N-1) return triangle[y][x];

int& ret = cache[y][x];

if (ret != -1)

return ret;

ret = max(solve(y + 1, x),solve(y + 1, x + 1)) + triangle[y][x]; // 2가지 경우의수중 더 큰 수와 자기 자신을 합쳐서 기록한다.

return ret;

}

void Init() {

for (int i = 0; i <= N; ++i)

for (int j = 0; j <= i; ++j)

cache[i][j] = -1;

}

int main()

{

cin >> N;

Init();

for (int i = 0; i < N; ++i)

for (int j = 0; j <= i; ++j)

cin >> triangle[i][j];

int ans =solve(0, 0);

cout << ans << endl;

return 0;

}