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

알고리즘 문제 풀이

문제

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

1932번: 정수 삼각형

---

풀이

DP 방식으로 접근한다.

점화식은 기본적으로 DP[i][j] = ARR[i-1][j] + MAX(DP[i-1][j], DP[i-1][j-1])이나 맨앞 맨끝의 경우는 비교 대상이 없으므로 DP[i][j] = ARR[i-1][j] +DP[i-1][j] || DP[i][j] = ARR[i-1][j] + DP[i-1][j-1] 을 조건문 처리로 해결했다

기본적으로 실버1의 난이도 문제치곤 점화식과 최전방 최후방의 두가지의 예외처리만 해주면 되는 간단한 문제였다

---

소스 코드

#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <cctype>
#include <set>
#include <string.h>

using namespace std;

int N, sum = 0;
int arr[501][501];
int dp[501][501];

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> arr[i][j];
			if(i == 0 && j == 0)
				dp[i][j] = arr[i][j];
			if (i != 0) {
				if (j == 0) {
					dp[i][j] = arr[i][j] + dp[i - 1][j];
				}
				else if (j == i) {
					dp[i][j] = arr[i][j] + dp[i - 1][j - 1];
				}
				else {
					dp[i][j] = arr[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1]);
				}
			}
		}
	}

	int max = 0;
	for (int i = 0; i <= N; i++) {
		if (dp[N-1][i] > max)
			max = dp[N-1][i];
	}

	cout << max;
}