[BOJ/백준 1932][C++] 정수 삼각형

문제

https://www.acmicpc.net/problem/1932

문제 내용

위에서부터 내려올 때, 아래 또는 오른쪽 아래 방향으로만 내려올 수 있다. (예제 입력 기준)

내려오면서 합이 최대가 되는 경로를 구하면 된다.

 

문제 풀이

이 문제도 역시 dp를 사용한다.

이 문제에서 dp를 채워나갈 때, 첫 번째 열은 무조건 위에서 내려오는 방법만 있다.
더불어, i==j인 곳은 무조건 대각선 방향으로만 내려올 수 있다.

위 두가지 경우를 제외하면, 아래 또는 오른쪽 아래 방향 중에서 더 큰 쪽을 선택하면 된다.

dp를 채우면서 max값을 따로 파악해주어야지 나중에 결과를 출력할 수 있다.

 

코드

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

int dp[505][505] = { 0, };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n; cin >> n;
	for (int i = 1; i <= n; i++) { //높이
		for (int j = 1; j <= i; j++) { //가로
			cin >> dp[i][j];
		}
	}

	//문제 해결
	int mmax = dp[1][1];

	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= i+1; j++) {
			if (j == 1) dp[i][j] += dp[i - 1][j] ;
			else if (j == i) dp[i][j] += dp[i - 1][j-1] ;
			else dp[i][j] += max(dp[i - 1][j-1], dp[i - 1][j]);
			mmax = max(mmax, dp[i][j]);
		}
	}
    
    	//결과 출력
	cout << mmax << '\n';
}