DIAMONDPATH 오답 질문입니다.

  • hyejinJ
    hyejinJ

    DIAMONDPATH를 DP를 사용하여 자신있게 풀어보았는데 오답이 떴네요ㅠㅠ
    아이디어는 N*N정사각형에 다이아몬드모양 데이터를 기울여서 집어넣고 위쪽과 왼쪽 데이터 값의 max를 자신의 값에 더해서 업데이트하는 식으로 코드를 짰습니다(solve부분).
    어디가 잘못되었을까요?ㅠ

    #include <iostream>
    #include "string.h"
    #include <algorithm>
    using namespace std;
    
    int d[100][100], N;
    
    int solve()
    {
        int i, j;
        for (i = 1; i < N; i++)
        {
            d[0][i] += d[0][i - 1];
            d[i][0] += d[i - 1][0];
        }
        for (i = 1; i < N; i++)
        {
            for (j = 1; j < N; j++)
            {
                d[i][j] += max(d[i - 1][j], d[i][j - 1]);
            }
        }
    
        return d[N - 1][N - 1];
    }
    
    int main()
    {
        int T;
        cin >> T;
        while (T--)
        {
            int i, j;
            cin >> N;
    
            for (i = 0; i < N; i++)//위쪽 삼각형 input받기
            {
                for (j = 0; j < i + 1; j++)
                {
                    cin >> d[i - j][j];
                }
            }
            for (i = N; i < 2 * N - 1; i++)//아랫쪽 삼각형 input받기
            {
                for (j = 0; j < 2 * N - 1 - i; j++)
                {
                    cin >> d[N - 1 - j][1 - N + j + i];
                }
            }
    
            cout << solve();
        }
        return 0;
    }
    

    8년 전
1개의 댓글이 있습니다.
  • hyejinJ
    hyejinJ

    정답 출력 부분에 엔터를 출력 안해서 그렇군요-_-; 부끄러워서 지우고 싶지만 비슷한 실수하신 분이 있을까 남겨놉니다...


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