DIAMONDPATH 오류입니다. 예제는 맞았는데요.

  • skylife927
    skylife927

    https://algospot.com/judge/problem/read/DIAMONDPATH
    1. 입력을 배열에 받는다.
    2. 맨 마지막 지점에서부터 위로 올라온다.
    3. 마지막에서 가운데까지는 위와 오른쪽위
    4. 가운데에서 맨 위까지는 왼쪽 위와 위의 값을 비교하여
    5. 가장 큰값을 sum에 대입하여 출력한다.

    #include <iostream>

using namespace std;

int arr[300][100];

int sum=0;

void dp(int N){
    //bottom up 방식으로 DP를 세워보자. 
    //2N-2부터 N-1까지는 위, 오른쪽 위
    sum = arr[2*N-2][0];
    int x=0;
    for(int i=2*N-2; i > N-1; i--){
        // 둘 중 큰것을 선택한다. 의미는 x값을 업데이트 한다.
        //arr[i-1][x]       arr[i-1][x+1]
        if(arr[i-1][x] > arr[i-1][x+1]){
            sum += arr[i-1][x];
        } else {
            sum += arr[i-1][x+1];
            x+=1;
        }
    }
    //N-1부터 0까지는 왼쪽 위, 위 규칙
    for(int i=N-1; i>=0; i--){
        // arr[i-1][x-1] arr[i-1][x]
        // x== 0이면 조취를 취해야 한다. 어떤 조취냐 
        // 무조건 첫번쨰껏을 끝까지 쭈욱 더해야 한다. 그리고 한방에 나가자

        if(x==0){
            for(; i>=0; i--){
                sum+=arr[i-1][0];
            }
            break;
        }
        if(arr[i-1][x-1] > arr[i-1][x]){
            sum += arr[i-1][x-1];
            x-=1;
        } else {
            sum += arr[i-1][x];
        }
    }
}

void init(){
    for(int i=0; i<300; i++)
        for(int j=0; j<100; j++)
            arr[i][j] = 0;
    sum=0;
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    cin >> T;
    for(test_case = 0; test_case < T; test_case++)
    {
        int N;
        cin>>N;
        init();
        int i = 0, j = 0;
        //위쪽 삼각형
        for(i=0; i<N; i++){
            for(j=0; j<=i; j++){
                cin>>arr[i][j];
            }
        }
        //아래쪽 삼각형
        for(;i<2*N-1; i++){
            for(j=0; j< 2*N - 1 - i; j++){
                cin>>arr[i][j];
            }
        }
        dp(N);
        cout<<sum<<endl;
    }
    return 0;
}

    8년 전
2개의 댓글이 있습니다.
  • skylife927
    skylife927

    그리디로 풀었습니다.
    dp로 하기 위해 이전의 값을 기억하도록 값을 저장하는 코드를 추가햇는데요. 그래도 안되네요 ㅋㅋ

    void dp(int N){
    //bottom up 방식으로 DP를 세워보자. 
    //2N-2부터 N-1까지는 위, 오른쪽 위
    sum = arr[2*N-2][0];
    int x=0;
    for(int i=2*N-2; i > N-1; i--){
        // 둘 중 큰것을 선택한다. 의미는 x값을 업데이트 한다.
        //arr[i-1][x]       arr[i-1][x+1]
        if(arr[i-1][x] + arr[i][x] > arr[i-1][x+1] + arr[i][x]){
            sum += arr[i-1][x];
            arr[i-1][x] += arr[i][x];
        } else {
            sum += arr[i-1][x+1];
            arr[i-1][x+1] += arr[i][x];
            x+=1;
        }
    }
    //N-1부터 0까지는 왼쪽 위, 위 규칙
    for(int i=N-1; i>=0; i--){
        // arr[i-1][x-1] arr[i-1][x]
        // x== 0이면 조취를 취해야 한다. 어떤 조취냐 
        // 무조건 첫번쨰껏을 끝까지 쭈욱 더해야 한다. 그리고 한방에 나가자

        if(x==0){
            for(; i>=0; i--){
                sum+=arr[i-1][0];
            }
            break;
        }
        if(arr[i-1][x-1] + arr[i][x] > arr[i-1][x] + arr[i][x]){
            sum += arr[i-1][x-1];
            arr[i-1][x-1] += arr[i][x];
            x-=1;
        } else {
            sum += arr[i-1][x];
            arr[i-1][x] += arr[i][x];
        }
    }
}

    8년 전 link
  • seico75
    seico75

    매순간 큰 값을 선택하는 것이 맞을까요?
    아래과 같은 예제에서는 어떻게 될지...
    1
    1 2
    9 1 2
    1 2
    1
    모든 path 에 대해서 저장을 해야 하는데 아래 dp 로 하신 것도 결국은 sum을 사용하기 때문에 본문에 쓰신 것과 달라질 것이 없네요.


    8년 전 link

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