글 읽기 - c++]예제나 질문게시판 테스트케이스는 다 돌아가는데 틀렸다고 나옵니다..

mimmyum 6년 전 0

어떤 부분에서 문제가 있을까요...

#include <iostream>

#define maxSize 1001
using namespace std;

int map[maxSize][maxSize];
int maxMap[maxSize][maxSize];

int main(){
    int N, M;
    int temp;
    int tempLeft[maxSize];
    int tempRight[maxSize];

    cin >> N >> M;

    for(int i = 0; i < N; i++){
        for(int j = 0;j < M;j++){
            cin >> temp;
            map[i][j] = temp;
        }
    }
    for(int j = 0; j<M; j++){
        tempLeft[j] = -2e9;
        tempRight[j] = -2e9;
    }

    temp = 0;
    for(int j = 0;j<M;j++){
        temp += map[0][j];
        maxMap[0][j] = temp;
    }

    for(int i = 1; i<N;i++){
        for(int j = 0; j<M; j++){
            maxMap[i][j] = maxMap[i-1][j] + map[i][j];
        }


        temp = maxMap[i][0];
        tempLeft[0] = temp;
        for(int j = 1; j<M; j++){
            temp += map[i][j];
            if(temp > maxMap[i][j]){
                tempLeft[j] = temp;
            }
            else{
                temp = maxMap[i][j];
            }
        }


        temp = maxMap[i][M-1];
        tempRight[M-1] = temp;
        for(int j = M-2; j>=0; j--){
            temp += map[i][j];
            if(temp > maxMap[i][j]){
                tempRight[j] = temp;
            }
            else{
                temp = maxMap[i][j];
            }
        }
        for(int j = 0 ; j<M;j++){
            if(tempLeft[j] > tempRight[j]){
                maxMap[i][j] = tempLeft[j];
            }
            else{
                maxMap[i][j] = tempRight[j];
            }
        }

        for(int j = 0; j<M; j++){
            tempLeft[j] = -2e9;
            tempRight[j] = -2e9;
        }
    }

    cout << maxMap[N-1][M-1] << endl;


}

djm03178 6년 전 1

아무 데이터나 막 넣어보는 건 질문자분도 충분히 하실 수 있습니다.

어디가 잘못됐는지에 대한 조언을 구하려면 코드의 동작 원리를 설명해야 합니다.

mimmyum 6년 전 0

@djm03178

아 네 푸는방식은 DP와 같이 풀었는데 한방향으로만 움직일 수 있으니까

원래 값들을 저장하는 map 배열과,

특정 점 (x, y)까지 가는 최대합을 저장하는 maxMap을 만들고,

두개의 임시 배열 tempLeft, tempRight를 만든 다음

tempLeft는 (x,0)부터 오른쪽으로 가면서 합이 가장 큰 값을 저장하고, tempRight는 (x, M-1)부터 왼쪽으로 가면서 합이 가장 큰 값을 저장하였습니다.

이 다음, tempLeft와 tempRight 중 큰 값을 maxMap 저장하고, (x+1) 라인에 (x)의 maxMap을 모두 저장합니다.

위 과정을 마지막 라인에 올때까지 반복하고 최종적으로 maxMap(N-1,M-1)을 출력하도록 하였습니다..

즉,

(x, y) ------------ㄱ

ㄴ-----------------(x+1,j)

일 때, maxMap(x+1, j)는 (x+1, j)까지 오는 최대의 합을 저장하였습니다.

위 과정에서 뭔가 빠진 로직이 있을까요?

djm03178 6년 전 0

3 3
1 1 -9
-9 1 -9
-9 1 1

이 케이스에서 5가 나와야 하는데, -5가 나옵니다.

문제를 찾자면, 반드시 좌우 맨 끝까지 갈 필요는 없는데 temp에 무조건 맨 끝부터 더한 값으로 최댓값을 찾기 때문에 최적의 답이 나오지 못합니다.

mimmyum 6년 전 0

@djm03178

답변 주셔서 감사합니다.

말씀대로 로직을 다시 살펴보니 tempLeft, tempRight 값이 제대로 바뀌지 않고 있더군요.

덕분에 풀었습니다. 감사합니다!!

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

문제

문제

출처

ICPC

c++]예제나 질문게시판 테스트케이스는 다 돌아가는데 틀렸다고 나옵니다..

mimmyum 6년 전 0

djm03178 6년 전 1

mimmyum 6년 전 0

djm03178 6년 전 0

mimmyum 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말