[백준/BOJ] 1932 - 정수 삼각형 (c++) (DP)

1. 문제

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

---

2. 풀이

이 문제는 DP를 이용하여 푸는 문제이다.

 

이번 dp배열은 2차원 배열을 사용할 것이다.

 

점화식부터 살펴보자면

 

초기값: dp[0][0] = tri[0][0]

 

(j=0) dp[i][j] = dp[i-1][j] + tri[i][j]

 

(j=i-1) dp[i][j] = dp[i-1][j-1] + tri[i][j] 

 

(1≤j≤i-2) dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j]

 

이다.

 

dp는 위에서부터 최대값을 구할 것이다.

 

자기자신의 위에 있는 왼쪽, 오른쪽 중 dp값의 더 큰 값을 구해 자기자신(tri[i][j])의 값과 더하면 dp[i][j]가 만들어지는 것이다.

 

하지만 맨 왼쪽 dp[i][0]과 맨 오른쪽 dp[i][i-1]값은 각각 왼쪽값과 오른쪽값이 없기에

 

그냥 dp[i][0]은 dp[i-1][0]을 더하고, dp[i][i-1]은 dp[i-1][i-2]값을 더하게 되는 것이다.

---

3. 소스코드

#include <iostream>

using namespace std;

int n, ans, tri[500][500], dp[500][500];

int main() {
	ios::sync_with_stdio(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> tri[i][j];
		}
	}

	dp[0][0] = tri[0][0];

	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= i; j++) {

			int l = j - 1, r = j;

			if (l < 0) dp[i][j] = dp[i - 1][r] + tri[i][j];
			else if (r >= n) dp[i][j] = dp[i - 1][l] + tri[i][j];
			else dp[i][j] = max(dp[i - 1][r], dp[i - 1][l]) + tri[i][j];

		}
	}

	for (int i = 0; i < n; i++) ans = max(ans, dp[n - 1][i]);

	cout << ans;
}

---

4. 참고

 

---

질문, 고칠점 등 댓글 언제나 환영입니다.