[알고리즘] 정수 삼각형 (백준, 1932)

문제

1932번: 정수 삼각형

 

 

풀이

ruhz3/CodingTest

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int map[500][500];
int cache[501][501];
int N;

int findMaxWay(int row, int col) {
	int &ret = cache[row][col];
	// 기저 사례 : 삼각형의 끝에 도달
	if (row == N - 1) {
		return ret = map[row][col];
	}
	// 메모이제이션
	if (ret != -1) {
		return ret;
	}
	// 두 갈래 길중에서 더 큰 길을 찾아 더함
	ret = map[row][col];
	int tmp = -1;
	for (int i = col; i <= col + 1; i++) {
		tmp = max(tmp, findMaxWay(row + 1, i));
	}
	ret += tmp;
	return ret;
}

int main() {
	cin >> N;
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> map[i][j];
		}
	}
	cout << findMaxWay(0, 0) << endl;

	return 0;
}

매번 선택에서 큰 것을 선택하기만 하면 된다고 생각하면 큰 오산이다. 더 큰 값을 골랐지만 그로 인해 다음 선택지가 훨씬 작아질 수도 있기 때문이다. 따라서 모든 경로를 비교해봐야 함을 알 수 있다. 그렇다면 완전 탐색을 먼저 생각해 볼 수 있다. 하지만 평소하던 완전탐색은 이 경우 불필요한 함수호출이 많아 비효율적이다.

탐색 도중, 표시한 8에서 7을 골라 아랫층으로 내려간다고 가정하자. 7에서 내려갈 수 있는 최대의 경로는 5이다. 표시한 1에서 7을 골라 내려간다고 하더라도 7에서 내려갈 수 있는 최대경로는 정해져있다. 그렇다면 굳이 7에서 함수를 호출할 필요 없이 8에서 호출했던 값을 사용하면 호출 횟수를 획기적으로 줄일 수 있을 것이다.

이런 방법을 동적계획법이라고 한다.

"cache[몇번째 행][몇번째 열] = 여기서 밑으로 내려갈 수 있는 최대 경로의 합"을 저장하여 해당 행열에 도착했을 경우, 바로 값을 반환한다면, 표시한 1에서 7로 내려갔을 때, 4행 2열이므로, cache[3][1]을 즉시 반환한다.