백준 알고리즘 1932번: 정수 삼각형 [C++]

문제 출처: www.acmicpc.net/problem/1932

1932번: 정수 삼각형

1. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int tri[501][501];
int dp[501][501];
int N;

int solution(int deep, int index)
{
	if (deep == N - 1) return tri[deep][index];		//맨 밑에 있는 요소에 접근했을 때
	if (!dp[deep][index])	// 대각선 왼쪽과 오른쪽의 값을 비교 후 더 큰 값을 현재 위치의 값을 더한 결과를 dp에 저장
		dp[deep][index] = max(solution(deep + 1, index), solution(deep + 1, index + 1)) + tri[deep][index];
	return dp[deep][index];		//dp의 값이 있거나 이미 처리가 된 경우
}

int main(void)
{
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < i + 1; j++)
			cin >> tri[i][j];

	cout << solution(0, 0);
	return 0;
}

(실행)

2. 풀이

tri 배열

우선 예제 입력을 입력을 하면 tri 배열은 위 그림과 같이 채워지게 된다.

dp 배열

그리고 초기의 dp 배열은 위 그림과 같다.

dp배열의 변화

위 그림처럼 맨 밑에서부터 위로 더하면서 올라가며 더 큰 값을 더한 결과를 dp에 저장하여 해답을 도출한다.

int main(void)
{
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < i + 1; j++)
			cin >> tri[i][j];

	cout << solution(0, 0);
	return 0;
}

입력받을 정수를 전부 입력을 받고 solution 함수를 실행한다.

int solution(int deep, int index)
{
	if (deep == N - 1) return tri[deep][index];		//맨 밑에 있는 요소에 접근했을 때
	if (!dp[deep][index])	// 대각선 왼쪽과 오른쪽의 값을 비교 후 더 큰 값을 현재 위치의 값을 더한 결과를 dp에 저장
		dp[deep][index] = max(solution(deep + 1, index), solution(deep + 1, index + 1)) + tri[deep][index];
	return dp[deep][index];		//dp의 값이 있거나 이미 처리가 된 경우
}

그리고 deep의 값이 N - 1과 동일할 때 삼각형의 마지막 위치까지 접근했기에 해당하는 tri배열의 위치에 있는 값을 반환한다. 그리고 만약 dp의 배열에 값이 저장이 안 되었다면 현재 위치에서 행을 증가시키고 열은 0과 1을 증가시킨 값을 비교 후 더 큰 값을 tri의 현재 위치의 값을 더한다. 그리고 dp값이 존재하거나 이미 없을 경우의 처리가 됐을 때 dp의 값을 반환한다.

3. 느낀 점

이번 문제를 풀고 동적 계획법이 아직도 나에게는 많이 어렵다고 느껴졌다. 단순한 백트래킹으로 구현하는 것은 쉬웠으나 이제 그렇게 제출을 하게되면 시간초과 메세지가 나온다. 그렇기 때문에 동적 계획법을 사용하여야하는데 어떻게 적용을 할지, 어떤 것을 저장할 지 그리고 재귀를 어떻게 호출할지 다양한 고민이 생겨났고 결국 풀지 못해서 다른 사람의 풀이를 보고 해결했다. 열심히 해야겠다.