[ BOJ / C++ ] 1932번 : 정수 삼각형

[ BOJ ] 1932번 : 정수 삼각형

문제 : https://www.acmicpc.net/problem/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번째 줄까지 정수 삼각형이 주어진다.

[  출력  ]

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

---

[  문제 접근 및 풀이  ]

각각 내려오면서 합이 최대가 되는 수들을 정리하는 다이나믹 프로그래밍 알고리즘이다.

따라서 가장 왼쪽에 있는 값을 구할 때는 대각선 오른쪽만 가능, 가장 오른쪽에 있는 값은 대각선 왼쪽만 가능해

더한 값을 넣어주었으며 가운데 있는 값들은 대각선 왼쪽, 오른쪽 값을 비교해서 현재 값에 더해주었다.

이후 마지막 열에서 최대값을 찾아 출력했다.

 

현 코드의 삼각형은 이렇게 생각해 풀었다.

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

 

현재 좌표가 (x,y)라고 했을 때 대각선 왼쪽은 (x-1,y-1), 대각선 오른쪽은 (x-1,y)이다.

 

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int dp[501][501];
int n;
void Q_1932();
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_1932();
}
void Q_1932(){
    cin >> n;
    for (int i = 0; i < n; i++) {
		for (int j = 0; j <=i; j++) {
			cin >> dp[i][j];
			if (i == 0) continue;
			else if (j == 0) {
				dp[i][j]+=dp[i - 1][j];
			}
			else if (j == i) {
				dp[i][j]+=dp[i - 1][j-1];
			}
			else { //4,4일 때 3,3이랑3,4
				dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j]);
			}
		}
	}
	int L = 0;
	for (int i = 0; i < n; i++) {
		L = max(dp[n - 1][i],L);
	}
	cout << L;
}

---