[C++] BOJ 1932 삼각형

문제

백준 1932번 The Triangle https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

코드

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

int triangle[501][501], dp[501][501];
int n;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> triangle[i][j];
		}
	}
	dp[1][1] = triangle[1][1];
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] = max(dp[i - 1][j] + triangle[i][j], dp[i - 1][j - 1] + triangle[i][j]);
		}
	}
	for (int j = 1; j <= n; j++)ans = max(ans, dp[n][j]);
	cout << ans;
}

풀이방법

dp를 이용해서 모든 경로에 대해 최대값을 갱신한다. 마지막에 n번째 줄에서 최대값을 출력해준다

고민과정

삼각형이라 입력받을때 살짝 헷갈렸다