글 읽기 - 어디가 틀렸는지 잘 모르겠어요.(c++)

112224 5년 전 1

알고리즘은 각 (i,j)에 대해서 최대값을 갱신해야 하는 경우는

1) 위에서(dp[i-1][j]+a[i][j])

2)왼쪽에서(dp[i][j-1]+a[i][j])

3)오른쪽에서(dp[i][j+1]+a[i][j])

위 세가지라고 생각하여 풀이를 진행했는데 최대값 비교를 위해 dp 테이블을 갱신하면 값이 이상해져

임시로 tmp에 그 값들을 담아두고 3가지 값중 최대값을 dp[i][j]로 설정하였습니다.(25~35 line)

값을 선택하면 경로를 하나 선택하게 되므로 재방문 하는 경우는 일어나지 않는다고 생각합니다.

게시판에 있는 케이스는 전부 확인해 봤는데 안나와요 ㅠㅠ

n=1000,m=1000 일때 모든 값 100, -100 두가지 경우도 맞게 나오는데...

어디가 틀렸을까요??

#include<iostream>
#include<algorithm>
using namespace std;
#define MM 1002
int dp[MM][MM];
int a[MM][MM];
int tmp[2][MM];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j];
    
    
    for(int j=1;j<=m;j++)        //첫번째 행 초기화.
    dp[1][j]=dp[1][j-1]+a[1][j];
    
    tmp[0][0]=tmp[0][n+1]=tmp[1][0]=tmp[1][n+1]=-987654321;    // i,j 가 범위를 벗어날 때 
                                                               // 설정하기 
    
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            tmp[0][j]=max(dp[i-1][j],tmp[0][j-1])+a[i][j];    //여기 (위에서 아래,->방향중 선택)
            int k=m+1-j;
            tmp[1][k]=max(dp[i-1][k],tmp[1][k+1])+a[i][k];    //여기 (위에서 아래,<-방향중 선택)
        }
        for(int j=1;j<=m;j++)
        dp[i][j]=max(tmp[0][j],tmp[1][j]);
    }
    cout<<dp[n][m]<<'\n';
    
}

112224 5년 전 0

문제는 22번 라인이었습니다. 지도 사이즈가 정사각 행렬일때는 위 코드도 맞습니다 ㅋㅋㅋㅋ

2일동안 고민했네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸는지 잘 모르겠어요.(c++)

112224 5년 전 1

112224 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말