3) 백준 1932 - 정수 삼각형

<문제>

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

예전에 한번 시도했다가 호되게 당하고 결국 이번에 풀어낸 문제. ㅎㅎㅎㅎㅎㅎㅎㅎㅎ

 

<코드>

#include <iostream>
#include <algorithm>

using namespace std;

int map[501][501] = {0, };
int memo[501][501] = {0, };
int Max = 0;

void dp(int cnt){
	for(int j = cnt; j > 0; j--){
		for(int i = 0; i < cnt; i++) {
			if(memo[j][i] > memo[j][i+1]) {
				memo[j-1][i] = map[j-1][i] + memo[j][i];
			}
			else {
				memo[j-1][i] = map[j-1][i] + memo[j][i+1];	
			}
		}
	}
	
	return;
}

int main(void) {
	int N;
	cin >> N;
	
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < i+1; j++){
			cin >> map[i][j];
		}
	}
	
	for(int i = 0; i < N; i++) {
		memo[N-1][i] = map[N-1][i];
	}
	
	dfs(N-1);
	
	cout << memo[0][0];
	
	return 0;
}

방법이 떠오르면 어렵지는 않지만, 방법을 어떻게 써야할지.... 헷갈렸던 문제였다.

 

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

위와 같은 삼각형이 있을 때 바텀업 형식으로 풀어나간다.

코드의 배열memo는 해당 위치에서 최댓값을 저장해 뒀는데 처음 가장 밑(해당 문제에서는 4 5 2 6 5 에 해당)에 있는 숫자들은 미리 저장해둔다.

memo[i][j] 를 적고 싶을때 memo[i+1][j]과 memo[i+1][j+1]을 비교해서 더 큰값과 map[i][j]와 더해서 memo[i][j]에 저장한다. 이런 식으로 맨 꼭대기 까지 올라간다.

 

처음에는 하나하나 다 해보는 방법으로 했는데 실패했다. 역시 시간 초과.

다음에는 밑에서 하나하나 다 해보는 방법을 했는데 밑부터 맨 위까지 올라가는 것을 반복하면서 최댓값을 저장했다.

역시 시간 초과.

결국 저 방법을 통해서 성공했다.

 

으..... ㅠㅠㅠㅠ

우웩.........

 

 

뿌-듯