https://www.acmicpc.net/problem/1932
문제
> 위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
> 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라.
> 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
> 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.접근
dp를 사용해서 각 수까지 왔을 때의 값을 각각 구해준다. 마지막 줄엔 해당 수까지 왔을 때 최종 값이 있을건데 그 값중 제일 큰 값을 정답으로 가지면 된다.
삼각형에서 왼쪽 끝에있는 경로는 반드시 아래층을 선택할 때 왼쪽만 골라서 온 경로고 오른쪽 끝 경로는 오른쪽만 쭉 골라서 온 경로이다.
이를 제외하고나면 나머지 경로는 반대로 생각해서 위층에서 내 경로 상의 위에 왼쪽과 오른쪽 중 더 큰값을 골라야 내가 최대값이 나온다. 이를통해 각각의 dp값을 구한다.
문제해결
> 이중벡터로 삼각형의 깂을 입력받는다. 아래로 갈수록 입력받는 벡터수가 늘어나므로 i값이 증가함에 따라 열의 크기를 맞게 설정해 입력받는다.
> dp를 선언하고 예제로 보면 첫 7값을 0,0에 넣고 반복문을 돌린다.
> 첫층은 끝났으므로 두번째층(i = 1)부터 한다.
매 층마다 j가 0이면 왼쪽만 골라온 애들이므로 전층의 dp[i-1][j](j가0이므로) 값에 현층 i,0값을 더해 준다.
> 그리고 j가i일때, 즉, 젤오른쪽 경로도 0과 같이 dp[i-1][j]에 현 층i,j값을 더해준다.
> 이제 가운데 경로들을 정의해줘야한다. 예를 들어 2층은 0, 1, 2가 있는데 0과 2는 위에서 처리했고 1을 구해보면 1은 1층에 있는 0과 1이 각각 오른쪽, 왼쪽을 선택했을 때 올수 있다. 즉 역으로 생각해서 2층의 1은 1층의 0과 1중 더 큰 값에서 온 경로로 고를 수 있다.
이를 max연산으로 비교해 더 큰값에 현층의 i,j를 더해준다.
> 3층이라면 1,2는 각각 2층의 0의 오른쪽, 1의 왼쪽중 큰거 1의 오른쪽, 2의 왼쪽중 큰거로 각각 구할 수 있다.
> 다 구하고나면 마지막 층엔 최종 결과가 저장되어있다. 이를 max연산으로 비교해 젤 큰값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> tri(n, vector<int>());
for (int i = 0; i < n; i++)
{
tri[i].resize(i + 1);
for (int j = 0; j <= i; j++) cin >> tri[i][j];
}
vector<vector<int>> dp(n, vector<int>(n, 0));
dp[0][0] = tri[0][0];
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
if (j == 0) dp[i][j] = dp[i - 1][j] + tri[i][j];
else if (j == i) dp[i][j] = dp[i - 1][j-1] + tri[i][j];
else dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + tri[i][j];
}
}
int rst = 0;
for (int j = 0; j < n; j++) rst = max(rst, dp[n - 1][j]);
cout << rst << '\n';
}
후기
도무지 해결 방식이 떠오르지 않아 어떻게 dp를 사용해야할지 공부했다. 모든 경로를 따져보고 개별적인 방법을 가진경로(0일때, i일때)는 따로 쳐리하고 공통규칙을 가진 경로에서 규칙을 구해 해결하는거다.
각 층마다 더 큰값으로 구해 경로를 구하는건 생각했지만 역으로 생각해서 아래층이 윗층을 고르는건 생각도 못했다. 이 생각을 못해서 현 층에 같은값이 어려개있으면 각각의 인덱스를 어떻게, 경로를 어떻게 하지?라는 문제에 막혔었다. 활용방식이 정말 무궁무진하다. 많이 접하고 많이 풀어봐야될거 같다.
