TrianglePath 문제 질문입니다.(C)

  • friend117
    friend117

    DP를 이용해서 풀이 했는데, 오답으로 나옵니다.
    어느 부분이 잘못되었는지 알 수 있을까요?

    #include

    #define MAX(a,b) (a > b) ? (a) : (b)

    int Array[101][101];
    int Answer[101][101];

    int N;
    int Max_Value;

    int main(void)
    {
    int test_case;
    int TC;
    int i, j;

    scanf("%d", &TC);
    
    for (test_case = 0; test_case < TC; test_case++)
    {
        Max_Value = 0;
    
        scanf("%d", &N);
    
        for (i = 0; i < N; i++)
        {
            for (j = 0; j <= i; j++)
            {
                scanf("%d", &Array[i][j]);
    
                if (i == 0)
                {
                    Answer[i][j] = Array[i][j];     //최초 값 입력
                }
                else
                {
                    if (j == 0)
                    {
                        Answer[i][j] = Answer[i - 1][j] + Array[i][j];      //가장 왼쪽의 값
                    }
                    else if (j == i)
                    {
                        Answer[i][j] = Answer[i - 1][j - 1] + Array[i][j];  //가장 오른쪽 값
                    }
                    else
                    {
                        Answer[i][j] = MAX(Answer[i - 1][j - 1], Answer[i - 1][j]) + Array[i][j];
                    }
    
                    if (Max_Value < Answer[i][j])
                    {
                        Max_Value = Answer[i][j];   //Max 값 찾기
                    }
                }
            }           
        }
    
        printf("%d\n", Max_Value);
    
        for (i = 0; i < N; i++)
        {
            for (j = 0; j <= i; j++)
            {
                Array[i][j] = 0;
                Answer[i][j] = 0;
            }
        }
    }
    
    return 0;

    }


    6년 전
2개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    MAX를 define macro로 사용하고 있는데,

    Answer[i][j] = MAX(Answer[i - 1][j - 1], Answer[i - 1][j]) + Array[i][j];

    에서 매크로가 풀리면

    Answer[i][j] = (Answer[i - 1][j - 1] > Answer[i - 1][j]) ? (Answer[i - 1][j - 1]) : (Answer[i - 1][j]) + Array[i][j]

    가 됩니다. Array[i][j]가 더해지는 경우는 뒷부분의 경우 뿐이 되기 때문에 오답이 나옵니다.

    MAX 매크로 전체를 괄호로 한번 감싸주시거나, algorithm에 있는 std::max를 사용하세요


    6년 전 link
  • friend117
    friend117

    감사합니다^^


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