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

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

 

dp의 정수인 정수 삼각형 문제이다.

 

dp란 공간을 활용하여 연산의 수를 줄이는 것이다.

 

또한 문제를 작게 나누어서 푸는것인데 이 문제에 아주 잘 나와있다.

 

우선 dp 행렬을 dp[501][501]로 선언하고 삼각형을 담을 배열 a또한 dp[501][501]로 선언해준다. (사실 삼각형이기 때문에 이 공간의 절반만 필요하지만 사용하기 편하게 이렇게 선언해준다.)

 

이중 for문을 통해 삼각형을 받아와주고 dp배열을 만들어 주면 되는데 dp[i][i]는 삼각형 a[i][i]원소까지의 최대값을 저장해준다.

 

따라서 dp[0][0] = a[0][0]이 되고 dp[1][0] = dp[0] + a[1][0], dp[1][1] = dp[0] + a[1][1]이다.

 

이 다음이 중요한데 선택지가 두개가 생기기 때문이다. dp[2][0]은 위에와 마찬가지로 dp[1][0] + a[2][0]이지만

 

dp[2][1]은 dp[1][0]과 dp[1][1]중 더 큰수를 선택하고 그 값과 a[2][1]을 더해준값이다. 

 

이런식으로 n-1까지 dp배열을 다 만들어 주었다면 이제 dp[n-1][0~n-1]까지의 값중 가장 큰값을 출력해주면된다.

 

#include <iostream>
#include <algorithm>
#define MAX 501
using namespace std;
int dp[MAX][MAX] = { 0, };
int a[MAX][MAX] = { 0, };
int main(int argc, char* argv[])
{
	int n;
	cin >> n;
 
	for (int i = 0;i < n;i++) {
		for (int j = 0;j <= i;j++) {
			cin >> a[i][j];
		}
	}
 
	dp[0][0] = a[0][0];
	dp[1][0] = dp[0][0] + a[1][0];
	dp[1][1] = dp[0][0] + a[1][1];
 
	for (int i = 2;i < n;i++) {
		for (int j = 0;j <= i;j++) {
			
			dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
		}
	}
	dp[n][0] = dp[n - 1][0];
	for (int i = 0;i < n;i++) {
		dp[n][0] = max(dp[n][0], dp[n - 1][i]);
	}
 
 
	cout << dp[n][0];
 
	return 0;
}

 

나는 이런식으로 코드를 짜보았고 마지막 대소 비교하는 부분이나 dp를 만드는 부분에는 차이가 있을 수 있을것 같다.

 

원리만 알면 간단하게 풀 수 있는 문제이다. 하지만 for문을 사용할 때 증감식을 잘못사용하여 코드를 고치면서 풀었다. 좀더 생각하고 코드를 짜는 버릇을 들이도록 하자.