1932번: 정수 삼각형

문제:

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력:

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

풀이:

• 이 문제는 다이나믹 프로그래밍에 메오이제이션 기법으로 바텀업 방식을 사용하여 풀었다. 우선 2차원 배열을 이용하여 입력 값을 모두 받고 해당 배열에 최대값을 저장해주면서 마지막 n까지 도달 해야 된다.

• 이 문제를 풀기 위한 핵심은 이 전 값들 두개 중에 한가지 길을 고를 수 있는데 이전 값 중에 최대값을 고른 뒤 현재 배열의 값과 더하여 저장 해주는 것이다. 이렇게 일부를 끝내 놓으면 for문을 돌면서 모든 경우의 수가 차곡 차곡 쌓이면서 최대값이 마지막에 나오는 것이다.

  🔍이것이 바로 다이나믹 프로그래밍으로 풀 수 있는 유형 1. 최적 부분 구조(Optimal Substructure)와 2. 중복되는 부분 문제(Overlapping Subproblem)의 경우이다. 각각에 대한 설명은 Dynamic Programming(동적 프로그래밍) 포스트를 확인하길 바란다.

• 마지막에는 모든 n가지 경우의 수를 돌면서 그 중 최대값을 저장해준 뒤 출력하면 된다.

코드:

#include <iostream>

using namespace std;

int main(){
	int n, answer=0, dp[501][501]={};
	//입력
	cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i; j++){ //n번째 줄마다 n개의 입력값이 있으므로 i까지 간다
			cin >> dp[i][j];
			//이전 값 두개 중에 큰 값을 고른 뒤 현재 값에 더한다
			dp[i][j] += max(dp[i-1][j-1],dp[i-1][j]);
		}
	}
	//모든 값들 중 최대인 경우 저장
	for(int i = 1; i <= n; i++) answer = max(dp[n][i], answer);
	//출력
	cout << answer;
}