[EPPER] 14회 9번

문제

 

---

풀이

 

유명한 동적계획법 문제들 중 하나이다. 위에서 아래로 내려가며 계산하는 방법이 있고, 아래에서 위로 올라가며 계산하는 방법이 있다. 후자가 훨씬 쉽고 간단하기 때문에 그 방법으로 풀었다.

 

맨 아랫줄에 대한 최대값은 자기 자신이니 그 윗줄부터 계산한다. 9의 경우엔 2와 7중 더 큰 수와 더하면 될 것이다. 4의 경우엔 7과 5 중에서 고르면 되겠다. 그런식으로 맨 위에 있는 6까지 갱신해준다. 새로운 matrix[0][0] 값을 반환하면 끝난다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int matrix[100][100];

int max(int a, int b) {
	if (a > b)
		return a;
	else
		return b;
}

int main() {
	int N;

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++)
			scanf("%d", &matrix[i][j]);
	}
	for (int i = N - 2; i >= 0; i--) { //아래부터 위로 올라감
		for (int j = 0; j <= i; j++) {
			matrix[i][j] = matrix[i][j] + max(matrix[i + 1][j], matrix[i + 1][j + 1]);
		}
	}
	printf("%d", matrix[0][0]);
}