[백준] 1932번 정수 삼각형 C++

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

14940번: 쉬운 최단거리

---

알고리즘 분류

 

Dynamic Programming

 

---

 

해설

 

 

#include <iostream>
using namespace std;

int main() {
	int N;
	cin >> N;
	int** triangle = new int* [N]; // 삼각형의 수를 저장하는 2차원 배열
	int** score = new int* [N]; // 합계를 저장하는 2차원 배열
	for (int i = 0; i < N; i++) {
		triangle[i] = new int[i+1];
		score[i] = new int[i+1];
		for (int j = 0; j < i+1; j++) {
			cin >> triangle[i][j];
		}
	}
	
	score[0][0] = triangle[0][0];


	// DP 알고리즘
	// 위에서 아래로 갈 때 맨 왼쪽과 오른쪽 수는 array 좌표 상으로 각각 [i-1][j], [i-1][j-1]에서 내려오는 경우만 존재
	// 사이에 있는 수는 좌우에서 올 수 있으므로 둘 중 더 큰 수와 더하면 됨
	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0) score[i][j] = score[i - 1][j] + triangle[i][j];
			else if (j == i) score[i][j] = score[i - 1][j - 1] + triangle[i][j];
			else {
				score[i][j] = max(score[i - 1][j-1], score[i - 1][j]) + triangle[i][j];
			}
		}
	}

	int max = 0; // 합이 최대가 되는 수 저장
	for (int i = 0; i < N; i++) { // 마지막 줄만 탐색
		if (score[N - 1][i] > max) max = score[N - 1][i];
	}
	cout << max;

	// 정답 코드X - 동적 할당이 끝난 후 제외시킬 때 씀
	delete[] triangle;
	delete[] score;
}

 

다이나믹 프로그래밍 알고리즘 관련 문제입니다

 

DP 문제는 규칙, 점화식을 찾아야 하는데

이 문제에서도

최대 합을 어떤 배열이나 자료형으로 가지고

합을 어떻게 계산하여(규칙) 진행할 방법 같이

다음 단계로 진행하면서 위의 정보를 저장하며 진행할

아이디어에 대한 고민을 했습니다.

 

저는 삼각형의 수를 저장할 배열과 같은 크기로 합 배열을 만들었고

합 배열의 규칙은 위의 코드와 같습니다.

 

백준 예제

사이에 껴있는 수는 좌우에서 각각 받으므로

더 큰 수를 받으면 자동으로 최대가 됩니다