글 읽기 - 60% 정도에서 틀렸다고 나오는데 어떤 케이스인지 모르겠어요....도저히ㅠ

yujjjang 6년 전 1

감사합니다.

주석으로 달아놓았어요 !

#include <iostream>
#include <vector>
using namespace std;
int main(){
  int a,b,c,cd,cc;
  cin>>a>>b;
  int sum=0;
  vector<vector<int> > w(a+1, vector<int>(b+1,0)); // 첫입력을 저장하는 배열.
  vector<vector<int> > dp(a+1, vector<int>(b+1,0)); // 각각 그 지점의 이동최대값을 저장하는 배열.
  for(int i=1;i<=a;++i){
    for(int j=1;j<=b;++j){
      cin>>c;
      w[i][j]=c;
      if(i==1) dp[i][j]+=dp[i][j-1]+c; 
      // 첫번째입력시 dp 값 간단히 더해주는 것으로 계산. (경로가 하나이므로)
    }
    if(i!=1){
        /**
        2번째줄부터 최대값 계산하는 방식이 틀린거같은데 무언가 틀렸는데 뭔지를 모르겠어요..
        왼쪽에서 오거나 오른쪽에서 오거나 위에서 오는거 이렇게 3가지로 나눠서 했는데
        왼쪽, 오른쪽에서 오는게 아래에 있는 2중 for문 2개인데.. 이게 좀 이상한데
        왜틀렸는지좀 알려주세요 ㅠㅠ
        **/
      for(int j=1; j<=b; ++j){
        for(int m=j-1;m>0;--m){
          cc+=w[i][m];
          sum=max(sum, dp[i-1][m]+cc);
        }
        
        cc=0;
        for(int m=j+1;m<=b;++m){
          cc+=w[i][m];
          sum=max(sum, dp[i-1][m]+cc);
        }
        cc=0;
        dp[i][j]= max(sum,dp[i-1][j]) + w[i][j];
        sum=0;
      }
    } 
  }
  cout << dp[a][b] << endl;
  return 0;
}