1932 숫자삼각형

DP 기초.

인덱스 문제 때문에 한참을 헷갈렸다.

특별한 알고리즘 없이 결국에 왼쪽으로 가느냐 오른쪽으로 가느냐 이부분 인덱싱 처리만 잘해주면 된다.

인덱스 계산이 가장 짜증난다나에겐...

코드:

#include <iostream>

using namespace std;

int arr[125251];

int D[125251];

int MAX(int a, int b)

{

return a > b ? a : b;

}

int height(int a)

{

int tmp = 0;

int ret = 0;

for (int i = 1; i <= 500; i++)

{

tmp += i;

if (a <= tmp){

ret = i;

break;

}

}

return ret;

}

int main()

{

int N , num = 0;

cin >> N;

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

{

num += i;

}

for (int i = 1; i <= num; i++)

{

cin >> arr[i];

}

D[1] = arr[1];

for (int i = 2; i <= num; i++)

{

int H = height(i);

int j;

for (j = i; j <= i + H - 1; j++)

{

if (i == j){

D[j] = D[j - H + 1] + arr[j];

}

else if (j == i + H - 1){

D[j] = D[j - H] + arr[j];

}

else{

D[j] = MAX(D[j - H + 1], D[j - H]) + arr[j];

}

}

i = j-1;

}

int max = 0;

for (int i = 1; i <= num; i++)

{

if (D[i] > max) max = D[i];

}

cout << max;

system("pause");

return 0;

}