글 읽기 - 왜 이런 방식은 안되는 거죠??

yoonfy4280 4년 전 0

제가 DP에 약하긴 하는데,,

이렇게 아래에서 위로 올라가는 방식으로 구현을 하고 생각해봤는데,, 틀렸다고 하는데 ㅠㅠ

어느 부분에 제가 논리적인 오류가 있는 것인지 잘 모르겠습니다.

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int T;
    cin >> T;
    
    while(T>0){
    
    int N;
    int item;
    cin >> N;
        
    int temp_N = N;
        
    int v[2][100002] = {0};
    int DP[2][100002] = {0};
    
    for(int i=0; i<2; i++){
        for(int j=1; j<=N; j++){
            cin >> item;
            v[i][j] = item;
        }
    }
    
    int loc = 1;
        
        DP[0][1] = v[0][1];
        DP[1][1] = v[1][1];
        DP[0][2] = DP[1][1] + v[0][2];
        DP[1][2] = DP[0][1] + v[1][2];
    
    if(N>=3){
       
        //맞아 떨어지는 곳 까지 DP를 반복적으로 만들어준다.
    while(loc <= N - (N%3) ){
        int plus= 0;
        
        for(int i=0; i<2; i++){
            
            if(i == 0){
                //아래부분으로 이동
                plus = 1;
            }
            else if( i== 1){
                //윗부분으로 이동
                plus = -1;
            }
            
            /*
            010
            101
            지그재그 형태의 더하기
            */
            int A = v[(i)+plus][loc] + v[(i)][loc+1] + v[(i) + plus][loc+2];
            
            /*
            001
            100
            이런 형태의 더하기
              */
            int B = v[(i)+ plus][loc] + v[(i)][loc+2];
            
            /*
            001
            010
            이런 형태의 더하기
            */
            int C = v[(i) + plus][loc+1] + v[(i)][loc+2];
            
            if(DP[i+plus][loc+2] < A + DP[i][loc-1]){
            DP[i+plus][loc+2] = DP[i][loc-1] + A;
            }
            
            if(B>=C && DP[i][loc+2] < B + DP[i][loc-1]){
                DP[i][loc+2] = DP[i][loc-1] + B;
            }
            else if(C>B && DP[i][loc+2] < C + DP[i][loc-1] ){
                 DP[i][loc+2] = DP[i][loc-1] + C;
            }
            
        }
        
        loc++;
        
    }
    //나머지가 하나 남았을 경우에
    if(N%3 == 1){
        //그 다음 것을 지그재그 형태로 더해준다.
        DP[0][loc] = DP[1][loc-1] + v[0][loc];
        DP[1][loc] = DP[0][loc-1] + v[1][loc];
        
    }
        //나머지가 두개 남았을 경우에
    else if(N%3 == 2){
        /*
        01       01
        10 이거와  00를 비교한다.
        */
        if( DP[0][loc-1] + v[1][loc] + v[0][loc+1] < DP[1][loc-1] + v[0][loc+1]){
            DP[0][loc+1] = DP[1][loc-1] + v[0][loc+1];
        }
        else{
            DP[0][loc+1] = DP[0][loc-1] +v[1][loc] + v[0][loc+1];
        }
        /*
        10        00
        01 이것과   01 비교한다.
        */
        if(DP[1][loc-1] + v[0][loc] + v[1][loc+1] < DP[0][loc-1] + v[1][loc+1]){
            DP[1][loc+1] = DP[0][loc-1] + v[1][loc+1];
        }
        else{
            DP[1][loc+1] = DP[1][loc-1] + v[0][loc] + v[1][loc+1];
        }
        
        
    }
        
    }

    int ANW;
    
    if(DP[0][N] < DP[1][N]){
        ANW = DP[1][N];
    }
    else{
        ANW = DP[0][N];
    }
    
        printf("%d\n",ANW);
        T--;
    }
    
    return 0;
}

1207koo 4년 전 0

코드가 복잡한데...

A와 B가 동시에 나오면 틀린 스티커 가져가기 방식 아닌가요?

010 001

101 100

이러면 아랫줄의 1이 붙어 있습니다.

이거보다 간단하게 풀 수 있긴 한데 기본적인 아이디어는 조금만 다듬으면 가능할 듯 합니다.

skysign 3년 전 0

문제풀이는 아래영상 참고하세요.

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

문제

문제

출처

ICPC

왜 이런 방식은 안되는 거죠??

yoonfy4280 4년 전 0

1207koo 4년 전 0

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말