[백준 1932] 정수 삼각형 풀이노트

1차 풀이 (2018-07-11, 시간초과)

완전탐색으로 풀이 시도.

* 위에서 부터 시작해서 왼쪽을 선택하는 경우와, 오른쪽을 선택하는 경우로 나누어 재귀적으로 해결.

	#include <iostream>
	using namespace std;
	int max(int a, int b) { return a > b ? a : b; }
	int get(int y, int x, int** tri);
	int N = 0, temp = 0;
	int main()
	{
	int **tri;
	//! 문제를 받아온다.
	cin >> N;
	tri = new int*[N];
	for (int i = 0; i < N; i++)
	{
	tri[i] = new int[i + 1];
	for (int j = 0; j < i + 1; j++)
	{
	cin >> tri[i][j];
	}
	}
	//! 재귀적으로 정답을 출력한다.
	cout << get(0, 0, tri);
	}
	//! 완전탐색.
	int get(int y, int x, int** tri)
	{
	//! 기저사항(1) : y가 범위를 벗어남 -> 삼각형의 맨 아랫층에 도달했음.
	if (N <= y) return temp;
	//! 기저사항(2) : x가 범위를 벗어남
	if (y < x) return 0;
	//! 왼쪽 아래와 오른쪽 아래를 선택하고, 큰 값을 반환.
	temp += tri[y][x];
	int left = get(y + 1, x, tri);
	int right = get(y + 1, x + 1, tri);
	temp -= tri[y][x];
	return max(left, right);
	}

view raw bj1932_1.cpp hosted with ❤ by GitHub

2차 풀이 (2018-07-11, 2912 KB, 36 MS)

점화식과 중복되는 부분문제를 캐싱하여 역방향으로 풀이 시도. 

* maxCost(i, j)가 최대값이 되기 위해서 maxCost(i-1, j)와 maxCost(i-1, j-1) 둘 중 큰 값을 선택하여 가산한다.

* 겹치는 부분문제가 생기므로 캐싱을 시도한다.

	#include <iostream>
	using namespace std;
	int max(int a, int b) { return a > b ? a : b; }
	int get(int y, int x, int** tri);
	int **cache;
	int main()
	{
	int **tri, N = 0;
	//! 문제를 받아온다.
	cin >> N;
	tri = new int*[N];
	cache = new int*[N];
	for (int i = 0; i < N; i++)
	{
	tri[i] = new int[i + 1];
	cache[i] = new int[i + 1];
	for (int j = 0; j < i + 1; j++)
	{
	cin >> tri[i][j];
	cache[i][j] = -1;
	}
	}
	//! 반대방향에서 탐색을 시작한다.
	int maxSum = 0;
	for (int i = 0; i < N; i++)
	{
	int temp = get(N - 1, i, tri);
	maxSum = max(maxSum, temp);
	}
	cout << maxSum;
	}
	int get(int y, int x, int** tri)
	{
	//! 기저사항(1) : y나 x가 범위를 벗어남.
	if (y < x || x < 0 || y < 0) return 0;
	//! 기저사항(2) : 캐싱되어 있음.
	if (cache[y][x] != -1) return cache[y][x];
	int ret = max(get(y - 1, x - 1, tri), get(y - 1, x, tri)) + tri[y][x];
	cache[y][x] = ret;
	return ret;
	}

view raw bj1932_2.cpp hosted with ❤ by GitHub

3차 풀이 (2018-07-11, 2384 KB, 32 MS)

2차 풀이에서 정방향으로 바꾸어 재귀호출 해소.

* maxCost(i, j)가 최대값이 되기 위해서 maxCost(i-1, j)와 maxCost(i-1, j-1) 둘 중 큰 값을 선택하여 가산한다

	#include <iostream>
	using namespace std;
	int max(int a, int b) { return a > b ? a : b; }
	int *cache;
	int *temp;
	int main()
	{
	int **tri, N = 0;
	//! 문제를 받아온다.
	cin >> N;
	tri = new int*[N];
	temp = new int[N];
	cache = new int[N];
	for (int i = 0; i < N; i++)
	{
	tri[i] = new int[i + 1];
	for (int j = 0; j < i + 1; j++)
	{
	cin >> tri[i][j];
	}
	}
	//! 순차적으로 각 경우의 합계를 계산한다.
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j <= i; j++)
	{
	temp[j] = max(j - 1 < 0 ? 0 : cache[j - 1], cache[j]) + tri[i][j];
	}
	for (int j = 0; j <= i; j++)
	{
	cache[j] = temp[j];
	}
	}
	//! 최대인 합계를 찾아 출력한다.
	int max = 0;
	for (int i = 0; i < N; i++)
	{
	if (cache[i] > max) max = cache[i];
	}
	cout << max;
	}

view raw bj1932_3.cpp hosted with ❤ by GitHub