DIAMONDPATH 문제 질문입니다.

  • gkwhdgns
    gkwhdgns

    안녕하세요.

    DIAMONDPATH 문제가 계속 오답이라 질문하려고 합니다.
    재귀적으로 문제를 해결하진 않았습니다.
    하지만 반복 과정에서 제일 아랫줄부터 이전 단계의 합계만을 저장하여 다음 단계로 넘어가기 때문에 끝까지 계산할 필요가 없는 동적 프로그래밍 방식이라고 생각합니다.
    (혹시 제가 알고있는 개념이 잘못되었다면 말씀해주세요.)
    그리하여 계산한 결과,
    예제의 값은 모두 알맞게 출력하지만 오답이라고 나오네요.
    아마 특별한 경우를 생각하지 못해서 그런게 아닐까 추측해보는데,
    잘못된 점을 발견하면 말씀 부탁드릴게요.
    도움이 필요합니다!!! 저는 못찾겠어요ㅜㅜ

    아래는 풀이 과정입니다.

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

void inputTableValue(short (*table)[100], int size){

    const int height = size*2 - 1;

    for(int i=0; i<height; i++){

        int width, value;
        if(i<size)  width = i + 1;
        else        width = height - i;

        for(int j=0; j<width; j++){
            scanf("%d", &value);
            table[i][j] = value;
        }
    }
}

int findPath(short (*table)[100], int size){

    const int height = size*2 - 1;
    int *sum = (int*)malloc(sizeof(int)*size);  
    int result;

    memset(sum, 0, sizeof(int));    

    for(int i=height-1; i>=0; i--){

        int width;
        int upperCase = 0;  
        int *newSum;

        if(i == height - 1){

            sum[0] = table[i][0];       

        }else{

            if(i<size-1){

                width = i + 1;
                upperCase = 1;

            }else{

                width = height - i;
                upperCase = -1;

            }

            newSum = (int*)malloc(sizeof(int)*width);
            memset(newSum, 0, sizeof(int)); 

            for(int j=0; j<width; j++){

                int a = sum[j];
                int b = 0;
                int bigger = 0;

                if(j+upperCase >= 0 && j+upperCase < width) b = sum[j+upperCase];                                       

                if(a >= b)  bigger = a;
                else        bigger = b;

                newSum[j] = bigger + table[i][j];

            }

            int* temp = sum;
            sum = newSum;
            newSum = temp;

            free(newSum);

        }
    }

    result = sum[0];
    free(sum);

    return result;
}

int main(){

    int num, size;
    scanf("%d", &num);

    for(int i=0; i<num; i++){

        short table[199][100];

        scanf("%d", &size);

        inputTableValue(table, size);

        int result = findPath(table, size);

        printf("%d\n", result);

    }
    return 0;
}

    감사합니다!


    8년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.