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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 1층부터 n층에 있을 때 현재 순서 수를 선택했을 때의 최대합을 2차원 배열 dp에 갱신하는 Bottom-Up 방식으로 풀었다.

1) 2차원 벡터인 nums를 선언해 각 층을 이루는 수들을 입력받아 저장한다.

2) 2차원 배열 dp를 선언하고, dp[1][0]을 nums[1][0]으로 초기화한다.

• dp[i][j] : i 번째 층의 j 번째 수를 선택했을 때 최대 합
• 1층에는 하나의 원소밖에 없기 때문에 해당 수 자체가 최대 합이 된다.

3) i가 2 ~ n일 때까지 경우의 수를 전부 갱신한다.

• 주어진 규칙에 의해 아래 층의 대각선 왼쪽 또는 대각선 오른쪽에 있는 수만 선택 가능
• 따라서 현재 층에 있는 현재 순서 수일 때의 최대합을 구하기 위해서는
  • 이전 층의 대각선 왼쪽 또는 오른쪽 수일 때 최대합 중 더 큰 값 + 현재 순서 수
    • 현재 순서 수가 층의 가장 첫 번째 수라면 대각선 오른쪽 수만 가능
    • 현재 순서 수가 층의 가장 마지막 수라면 대각선 왼쪽 수만 가능
• 위 과정을 점화식으로 나타내면
  • i : 현재 층 / j : 현재 순서 수 라고 할 때
  • if(j == 0) dp[i][j] = dp[i - 1][j] + nums[i][j]
  • else if(j == nums[i].size()) dp[i][j] = dp[i - 1][j - 1] + nums[i][j]
  • else dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + nums[i][j]

4) 따라서 2부터 n까지 모든 i에 대해 각 순서 수일 때의 최대합을 dp에 갱신해가면
dp[n][0] ~ dp[n][n - 1]에 저장되는 값 중 가장 큰 값이 최대 합이 된다.

🖥️ 풀이 코드

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

int n;
int dp[1001][3];	// dp[i][j] : i번째 집에서 j색으로 칠했을 때의 최소 비용
vector<vector<int>> costs;

void solution()
{
	for (int i = 0; i < 3; i++)
		dp[1][i] = costs[1][i];

	for (int i = 2; i <= n; i++)
	{
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
	}

	cout << min({ dp[n][0], dp[n][1], dp[n][2] });
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	costs.resize(n + 1);

	for (int i = 0; i < n; i++)
		costs[0].push_back(0);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int cost;
			cin >> cost;
			costs[i].push_back(cost);
		}
	}
	solution();
}