백준 1932 정수삼각형 (C++)

탑다운방식과 바텀업 방식 첨부.

삼각형 형태로 구성된 수를 한칸씩 타고 내려오며 총 합이 가장 큰 경로의 합을 찾는 문제

얼핏 보면 그리디로 풀 수도 있을 것 같지만

좌측처럼 그리디하게 당장 큰 것을 찾아 내려가면 실제로 가장 큰 경로가 되지 않는다.

많은 경우의 수를 비교하기 위해 dp를 사용해서 풀어야 했던 문제.

 

맨 위칸 값을 기준으로 시작해서 다음행의 같은열과 다음 열 값을 확인 해 더 큰 값을 dp에 저장한다.

마지막 행에 도달하면 해당 위치의 값을 그대로 반환해주면 될 것이다.

 

top-down 방식 풀이

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int arr[501][501];
int dp[501][501];
int inputnum;
int rec(int row,int col);
int main()
{
	cin >> inputnum;
	for (int i = 0; i < inputnum; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			cin >> arr[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << rec(0,0);
}
int rec(int row, int col)
{
	if (row >= inputnum) return -1;
	if (row == inputnum - 1) return arr[row][col];
	if (dp[row][col] != -1) return dp[row][col];
	int temp = arr[row][col] + max(rec(row + 1, col),rec(row + 1, col + 1));
	//cout << "row: " << row << " col: "<< col << " temp: "<<temp<< endl;
	dp[row][col] = temp;
	return temp;
}

memset 함수로 이차원 배열 dp의 모든 값을 -1로 초기화 해준 뒤

[0][0]부터 값을 기록한다. 다음행의 대각선 아래 두 값중 큰 값을 찾아서 기록해준다.

 

bottom-up 풀이

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int arr[501][501];
int dp[501][501];
int inputnum;
int main()
{
	cin >> inputnum;
	for (int i = 0; i < inputnum; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			cin >> arr[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	dp[0][0] = arr[0][0];
	for (int i = 0; i < inputnum-1; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			dp[i + 1][j] = max(dp[i+1][j],dp[i][j] + arr[i + 1][j]);
			dp[i + 1][j+1] = max(dp[i+1][j+1],dp[i][j] + arr[i + 1][j+1]);
		}
	}
	int temp = -1;
	for (int i = 0; i < inputnum; i++)
	{
		temp = max(temp, dp[inputnum - 1][i]);
	}
	cout << temp;
}

탑다운 방식에서는 맨아래까지 재귀로 쭉 타고 내려가서 마지막 줄의 값을 받아서 사용했고

 

바텀업 방식에서는 arr[0][0] 값을 dp[0][0] 자리에 저장해두고 한칸씩 내려가며 값을 기록해가면서

이전 칸의 값을 활용하며 만들어나갔다. 마지막줄까지 가는데의 최대 비용을 저장해두고

dp배열의 마지막 행을 검사해 가장 큰 값을 출력해주었다.