[소프티어] 나무수확 (C++)

👓 문제 설명

---

https://softeer.ai/app/assessment/index.html?xid=142803&xsrfToken=79lTRdbS0H0nbjSEJkkn2aX8l6GyHgUG&testType=practice

---

💣 제한 사항

---

🚨 접근 방법

우,하 2 방향으로 (0,0)에서 1칸씩 이동할 때 (n-1,n-1) 지점에 도착하였을 때
최대 경로값을 구하는 문제이다.

단순히, BFS 및 다익스트라를 이용해 풀어볼 수 있겠지만
이전에 지나온 경로를 다시 돌아가야하는 경우가 발생하기 때문에 시간초과가 발생했다.

따라서, 2방향으로만 이동하는 조건을 이용하여 DP로 해결했다.

특정한 지점의 값을 2배하였을 때의 누적 합이므로
2개의 경우로 나누어 DP를 진행해야한다.

1. 특정 지점 값을 2배 하지 않은 경로 누적합이 최대일 때
2. 특정 지점 값을 2배 하였을 때 경로 누적합이 최대일 때

이렇게 2가지를 각각 구해야 하는 이유는 다음과 같다.

특정 지점 값을 2배하였을 때 최대 경로만 이용하여 구했을 때
만약 새로운 지점에서 2배하였을 때 갱신되는 경우
현재 지나온 경로가 최대라는 보장을 할 수 없기 때문이다.
즉, 특정 지점을 2배하지 않은 경로가 다음 지점에서 2배하여 더했을 때 경로 누적합이 최대가 되는 경우가 존재한다는 뜻!

---

🚈 풀이

#include<iostream>
#include<algorithm>
// 최댓값을 포함하는 경로
// 최댓값을 포함하지 않는 경로
// 경로누적값이 최대인 경우 vs 특정 좌표가 최대인 경우 비교
using namespace std;
int n;
int arr[1001][1001];
struct info{
    int sum,max_v;
};
info dp[1001][1001];
info dp2[1001][1001];
void func(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            // 경로 누적값이 최대인 경우
            if(dp[i-1][j].sum>=dp[i][j-1].sum){
                dp[i][j].sum=dp[i-1][j].sum+arr[i][j];
                dp[i][j].max_v=max(dp[i-1][j].max_v,arr[i][j]);
            }
            else{
                dp[i][j].sum=dp[i][j-1].sum+arr[i][j];
                dp[i][j].max_v=max(dp[i][j-1].max_v,arr[i][j]);
            }
            // 특정 좌표가 최대인 경우
            if(dp2[i-1][j].max_v+dp2[i-1][j].sum>=dp2[i][j-1].max_v+dp2[i][j-1].sum){
                if(dp2[i-1][j].max_v>=arr[i][j]){
                    dp2[i][j].sum=dp2[i-1][j].sum+arr[i][j];
                    dp2[i][j].max_v=dp2[i-1][j].max_v;
                }
                else{
                    dp2[i][j].sum=dp2[i-1][j].sum+arr[i][j];
                    dp2[i][j].max_v=arr[i][j];
                }
            }
            else{
                if(dp2[i][j-1].max_v>=arr[i][j]){
                    dp2[i][j].sum=dp2[i][j-1].sum+arr[i][j];
                    dp2[i][j].max_v=dp2[i][j-1].max_v;
                }
                else{
                    dp2[i][j].sum=dp2[i][j-1].sum+arr[i][j];
                    dp2[i][j].max_v=arr[i][j];
                }
            }
        }
    }
    cout<<max(dp[n][n].sum+dp[n][n].max_v,dp2[n][n].sum+dp2[n][n].max_v);
}
int main(int argc, char** argv)
{
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>arr[i][j];
        }
    }
    func();
   return 0;
}