[백준] 알고리즘 1932번 - 정수 삼각형 문제

문제

소스코드

#include <bits/stdc++.h>
using namespace std;
int arr[501][501];
int dp[501][501];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
				cin >> arr[i][j];
		}
	} 
	dp[0][0] = arr[0][0];
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0) dp[i][j] = dp[i - 1][j] + arr[i][j];
			 
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans = max(ans, dp[n-1][i]);
	}
	cout << ans;
}

풀이

                  7

              3       8

       8          1          0

 

dp[i][j] i번째줄의 j번을 선택하였을 때 arr[i][j] + dp[i-1][j-1] or dp[i-1][j] 중 최대값을 골라서 저장한다.

즉 각각의 경우의수를 저장하여 n번째 줄 까지 갈 수 있는 경우들의 결과 값들을 저장한다.

우선 윗층 요소는 아래쪽의 대각선 왼쪽 방향과 오른쪽 방향을 선택할 수 있다.

이를 배열로 옮기면 arr[i][j]가 아래의 요소를 선택할 수 있는 경우의 수는 arr[i+1][j] arr[i+1][j+1]의 경우가 있다.

이는 직접 눈으로 살펴보면 이런식으로 선택된다는 것을 알 수 있다.

 

여기서 

j가 0인 경우는 선택할 수 있는 가지 수가 무조건 아래인 요소 밖에 없으니 이 부분만 처리해주면된다.

그리고 나머지 경우는 젤 오른쪽 끝부분은 어짜피 그 윗부분들이 0으로 초기화 되있으니 최대값 비교를 그냥 진행해주면 된다.