글 읽기 - 인풋에 0~9 이외의 숫자가 들어가는 것 같아요.

dominyellow 8년 전 0

DP에 슬라이딩 윈도우기법으로 캐시 배열 크기를 줄여서 메모리 초과를 해결했는데요.

원래 배열이 [2][3] 의 배열만 있으면 가능하지만 코딩의 편의성 때문에 배열을 양 옆으로 1칸씩 더 할당하는 버릇이 있습니다.

[i][j]원소에 대한 최댓값(최솟값) 합을 구한다고 할 때, [i-1][j-1], [i-1][j], [i-1][j+1] 이 3개의 값과의 합을 비교하도록 짰구요
왼쪽은 [i-1][j-1]을 참조하지 않고, 맨 오른쪽은 [i-1][j+1]을 참조하면 안되기 때문에 배열의 양 끝값을 -1, 혹은 99로 초기화 했습니다.
숫자가 0~9의 숫자만 들어가기 때문에 최댓값을 구할때는 그보다 작은 -1, 최솟값을 구할때는 그보다 큰 99 (사실 10이여도 될것이라고 생각)로
양쪽 끝값을 초기화했는데 자꾸 오답이나서.....

그래서 몇시간째 같은코드만 제출하다가 양쪽 끝값을 매우크거나 매우작은 값으로 초기화를 했는데 정답이 나왔습니다.

제가 문제를 잘못 이해한건지, 문제는 이해했지만 양쪽 끝값의 벽 역할을 하는 숫자를 선택하는 과정에서 틀린점이 있는지 궁금해서 질문 드립니다.

#include <stdio.h>
#include <algorithm>
  
using namespace std;
  
int N;
int f1[2][5];
int f2[2][5];
  
int max3(int a, int b, int c){
    return max(a, max(b, c));
}
  
int min3(int a, int b, int c){
    return min(a, min(b, c));
}
  
int main(void){
    scanf("%d", &N);
  
    int _min, _max;
  
    f1[0][0] = f1[0][4] = f1[1][0] = f1[1][4] = -1;
    f2[0][0] = f2[0][4] = f2[1][0] = f2[1][4] = 99;
     
    //이 부분을 초기화 하는 부분을 변경했더니 정답 처리
    //f1[0][0] = f1[0][4] = f1[1][0] = f1[1][4] = -978987987;
    //f2[0][0] = f2[0][4] = f2[1][0] = f2[1][4] = 987987987;
     
  
    for(int i=1; i<=N; i++){
        for(int j=1; j<=3; j++){
            scanf("%d", &f1[1][j]);
            f2[1][j] = f1[1][j];
        }
        for(int j=1; j<=3; j++){
            f1[1][j] = max3(f1[1][j] + f1[0][j-1], f1[1][j] + f1[0][j], f1[1][j] + f1[0][j+1]);
            f2[1][j] = min3(f2[1][j] + f2[0][j-1], f2[1][j] + f2[0][j], f2[1][j] + f2[0][j+1]);
        }
        //printf("[%d %d %d] [%d %d %d]\n", f1[1][1], f1[1][2], f1[1][3], f2[1][1], f2[1][2], f2[1][3]);
        for(int j=1; j<=3; j++){
            f1[0][j] = f1[1][j];
            f2[0][j] = f2[1][j];
        }
    }
  
    _max = max3(f1[1][1], f1[1][2], f1[1][3]);
    _min = min3(f2[1][1], f2[1][2], f2[1][3]);
  
    printf("%d %d\n", _max, _min);
  
    return 0;
}

yukariko 8년 전 1

제가 맞은코드에 0~9사이 숫자가아니면 오류를반환하게 코드를고쳐서 제출해봤는데

맞았습니다가 뜬것으로 보아 입력에는 문제가 없어보입니다.

dominyellow 8년 전 0

마자여.. 저두해봤어요 ㅠㅠㅠㅠㅠㅠ

맞아놓고도 왜틀렸는지 생각해야겠어요.. 감사합니다.

jbs30_jsh 2년 전 0

37, 38 줄에서 max, min 처리할 때 그 함수가 처리하는 값들은 i=1부터의 누적 값이기 때문에 0부터 9 사이의 수가 아니게 됩니다. 따라서 max 처리시에는 최소한 9*10^5보다 큰 수로 처리해야겠네요.

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