💎 문제
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번째 줄까지 정수 삼각형이 주어진다.
💎 출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
💎 풀이 방법
저번 게시글에서 풀었던 dp문제와 굉장히 유사하다고 생각된다!! 그래서 빠르게 틀을 잡고 쉽게 풀어낼 수 있었던 문제였던 것 같다. 이번에 풀게 되면서 dp는 정말 많이 풀어볼 수록 접근이나 해결에 능숙해질 수 있다는 것도 다시금 깨닫게 되었다.
문제는 이차원 배열에 저장되어 구성된 정수 삼각형에서 어떤 경로로 수를 선택해서 최대의 합을 이끌어낼 수 있을지 확인하는 것이었다. 이 때 경로는 두 가지 길이 있는데 다음 삼각형의 행으로 이동하면서 현재 위치와 같은 인덱스를 가진 배열을 선택하거나 혹은 그 보다 1더 큰 배열로 이동하거나 두 가지 경로가 있다.(이는 우측 대각선이나 좌측 대각선 방향으로 이동하는 것)
따라서 최대가 되기 위해서는 dp를 맨 아랫줄부터 시작해서 구해나간다면 최대가 되는 경로는 반드시 하나일 것이기 때문에 아래에서 위로 올라가는 코드로 구성하였다.
밑에서부터의 행을 점검하면서 맨 아래의 dp의 값은 현재의 입력받은 배열의 값이 될 것이며 한 층씩 올라가면서 점검할 것이다. 위의 층으로 넘어가게 되었을 때
dp[i][j] = max(dp[i + 1][j],dp[i + 1][j + 1]) + v[i][j];위와 같이 이전 층의 dp값들에서 대각선 방향에 있는 두 값중 큰 것을 현재 배열과 더해주어서 dp의 값을 계산해 나갈 수 있었다.
💎 전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int dp[501][501];
vector <vector <int>> v(500, vector<int>(500));
int main(int argc, const char * argv[]) {
int temp;
cin >> n;
for(int i = 0;i < n;i++){
for(int j = 0;j <= i;j++)
{
cin >> temp;
v[i][j] = temp;
}
}
for(int i = n - 1;i >= 0;i--){
for(int j = i;j >= 0;j--){
if(i == n - 1)
dp[i][j] = v[i][j];
else{
dp[i][j] = max(dp[i + 1][j],dp[i + 1][j + 1]) + v[i][j];
}
}
}
cout << dp[0][0] << "\n";
return 0;
}
💎 고민
생각보다 매우 이지하게 풀 수 있었는데 이전 게시글의 문제와 유사해서도 있었던 것 같고 접근 방법에서 맨 맽층 부터 차근차근 올라가서 경로를 구하는 방식이 편리하게 잘 작용한 것 같다. 이차원배열의 dp문제를 두번 연속 풀게되었는데 이제 다음 문제는 dp 말고 다른 유형의 알고리즘을 풀어보도록 하겠다!!
화팅!
