[백준] 1932번 정수 삼각형 - C++ (dp, bottom-up)

발상

너무 길어서 잘 짠 코드는 아닌 거 같지만.. 그래도 풀이를 남겨본다.

우선 이차원 배열을 써야겠다고 생각함 (삼각형 형태니까)

dp와 주어진 값을 받는 배열 모두 이차원 배열로 선언했다. 

 

dp[i][j]에 대한 점화식은 세가지 경우로 나뉜다.

 1) j>1이고 j<i인 경우: 이 경우, 적용할 수 있는 루트가 두가지이다. 따라서 dp[i-1][j]와 dp[i-1][j-1] 중 최솟값을 고르고 거기에 현재의 값을 더해주면 최소 경로가 된다. 

 2) j=1인 경우: 한가지 선택밖에 없다. dp[i-1][j]

 3) j=i인 경우: 마찬가지로 한가지 선택뿐. dp[i-1][j-1]

 

이것을 코드로 구현하여 문제를 해결했다. 

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	int N;
	cin >> N;
	int dp[N+1][N+1];
	int route[N+1][N+1];
	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=i; j++){
			cin >> route[i][j]; 
		}
	}
	vector <int> ans;
	for(int i=1; i<=N; i++){
		if (i==1) dp[i][i] = route[1][1];
		else {
			for(int j=1; j<=i ;j++){
				if (j>1 && j<i) {
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + route[i][j];
				}
				else if (j==1){
					dp[i][j] = dp[i-1][j] + route[i][j];
				}
				else if (j==i){
					dp [i][j] = dp[i-1][j-1] + route[i][j];
				}
			}
		}
		if (i==N) {
			for (int j=1; j<=N; j++){
				ans.push_back(dp[i][j]);
			}
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans[N-1];
}

dp 구현부분만 살펴보면 다음과 같다.

base case는 dp[1][1] = route[1][1]이다.

이외에는 앞서 말한 세 가지 경우로 나누어 dp[i][j] 값을 계산하였다. 

	for(int i=1; i<=N; i++){
		if (i==1) dp[i][i] = route[1][1];
		else {
			for(int j=1; j<=i ;j++){
				if (j>1 && j<i) {
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + route[i][j];
				}
				else if (j==1){
					dp[i][j] = dp[i-1][j] + route[i][j];
				}
				else if (j==i){
					dp [i][j] = dp[i-1][j-1] + route[i][j];
				}
			}
		}
		if (i==N) {
			for (int j=1; j<=N; j++){
				ans.push_back(dp[i][j]);
			}
		}
	}

최대 경로를 구하라고 했으므로, 마지막 줄의 경로값에 해당하는 dp[N][1~N] 값들 중 최댓값을 찾으면 정답이다. 

	sort(ans.begin(), ans.end());
	cout << ans[N-1];