1932: 정수 삼각형

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

1932번: 정수 삼각형

설명

맨 위층에서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 작성.

핵심 아이디어

• 다이나믹 프로그램이
• 작은 문제부터 먼저 풀자!
• 맨 왼쪽 계산과 맨 오른쪽 계산 그리고 중간을 max() 활용해서 비교해주면 된다!

출처: https://coooco.tistory.com/105

1. 맨 왼쪽인 경우(j=0): dp[i][j] += dp[i-1][j]
2. 맨 오른쪽 인 경우(j=맨끝): dp[i][j] += dp[i-1][j-1]
3. 가운데 경우는 max()활용: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) 

코드 구현

n = int(input())
dp = []
for i in range(n):
	dp.append(list(map(int, input().split())))

# 맨 위 정수를 그위에 더해줄 값이 없어서 i=1부터 시작
for i in range(1, n):
	for j in range(i+1): # j=0~
		if j == 0: # 맨 왼쪽
			dp[i][j] += dp[i-1][j]
		elif j == i: # 맨 오른쪽
			dp[i][j] += dp[i-1][j-1]
		else: # 중간에 있다면
			dp[i][j] += max(dp[i-1][j], dp[i-1][j-1])
print(max(dp[n-1]))

C++

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

int dp[501][501]; // 다이나믹 프로그래밍을 위한 DP 테이블 초기화

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	// 삼각형 입력받기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			cin >> dp[i][j];
		}
	}

	// 첫줄을 제외하고 2층부터 시작
	
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0) { // 가장 왼쪽이라면
				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]);
			}
		}
	}

	int max_value = 0;
	// 마지막 줄에서 최댓값 출력
	for (int i = 0; i < n; i++) {
		max_value = max(max_value, dp[n - 1][i]);
	}
	cout << max_value;


}