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

 

알고리즘 분류: 다이나믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

 

 

【 풀이 】

 

삼각형의 규칙을 구하면 된다.

2차원 배열 dp에 입력 받고,

각 칸까지 선택된 수의 합을 각 칸에 다시 저장한 2차원 배열을 dp라고 하자.

dp[1][1] = dp[1][1]

dp[2][1] = dp[1][1] + dp[2][1],  dp[2][2] = dp[1][1] + dp[2][2] 이다.

 

3번째 층부터, 가운데의 수들은 양쪽 대각선에 저장된 숫자 중 가장 큰 값과 더해져야 한다. 즉,

 

dp[3][1] = dp[2][1] + dp[3][1],  dp[3][2] = max(dp[2][1], dp[2][2]) + dp[3][2],  dp[3][3] = dp[2][2] + dp[3][3]

dp[4][1] = dp[3][1] + dp[4][1],  dp[4][2] = max(dp[3][1], dp[3][2]) + dp[4][2],  dp[4][3] = max(dp[3][2], dp[3][3]),  dp[4][4] = dp[3][3] + dp[4][4]

 

여기서 일반화를 해보면,

dp[i][1] = dp[i - 1] + dp[i][1]

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

dp[i][i] = dp[i -1][j - 1] + dp[i][j]

 

 

 

【 코드 】

 

#include<iostream>
#include<algorithm>
using namespace std;

int arr[501][501];
int dp[501][501];

int main() {
	int n, max_num = 0;
	cin >> n;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			cin >> arr[i][j];

	dp[1][1] = arr[1][1];
	dp[2][1] = dp[1][1] + arr[2][1];
	dp[2][2] = dp[1][1] + arr[2][2];

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if (j == 1)
				dp[i][1] = dp[i - 1][1] + arr[i][1];
			else if (j == i)
				dp[i][j] = dp[i - 1][i - 1] + arr[i][j];
			else
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
			max_num = max(max_num, dp[i][j]);
		}
	}

	cout << max_num;

	return 0;
}