[동적계획법, 난이도 하] 백준 1932번 정수 삼각형

동적계획법을 처음 배우는 분들이 동적계획법에 대해 감을 익히기 적합한 난이도의 문제이다.

이 문제보다 쉬운 DP문제는 포스팅하지 않을 것이다.

 

입력은 인덱스 0부터가 아닌 1부터 시작한다.

DP는 대체로 이런 식으로 입력해야 편한 것 같다.

아래 표는 예제 입력1을 기준으로 작성했다.

 

INPUT[1][1]값은 DP[1][1]에 그대로 넣어주고 (1년전에 본인이 짠 아래 소스코드에서는 DP배열이름을 root로 했다)

인덱스 2부터 DP를 수행하여 DP[i-1][j-1]와 DP[i-1][j]중 최댓값과 INPUT[i][j]를 더해서 DP배열을 채워나가면 된다.

 

모든 과정을 마친 최종 DP 표이다.

 

 맨 아래 5행의 요소들중 최댓값 30이 이 케이스의 답이 된다.

 

#include <iostream>
#include <math.h>
using namespace std;
int root[501][501];
int input[501][501];
int max(int a, int b) {
	if (a > b) return a;
	else return b;
}
int main() {
	int a;
	cin >> a;
	for (int i = 1; i < a + 1; i++) {
		for (int j = 1; j < i + 1; j++) {
			cin >> input[i][j];
		}
	}
	root[1][1] = input[1][1];
	for (int i = 2; i < a + 1; i++) {
		for (int j = 1; j < i + 1; j++) {
			root[i][j] = max(root[i - 1][j - 1], root[i - 1][j]) + input[i][j];
		}
	}
	int base = root[a][1];
	for (int i = 2; i < a + 1; i++) {
		if (root[a][i]>base) base = root[a][i];
	}
	cout << base;
}