[C++,DP] 백준 9465번 스티커 문제풀이

문제 링크

백준 9465번 스티커

9465번: 스티커

 

"1로 만들기"와 같은 유형의 DP 문제이다.

처음에 in-place로 알고리즘을 짜려다 꼬여서 자꾸 오답이 나오길래 각설하고 그냥 따로 배열을 하나 더 만들어서 짜서 AC를 받았다. 첫번째 코드는 미완성인 in-place 코드이고 두번째는 배열을 하나 더 만들어서 짠 정답코드이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; 
 
int main(){
    int T;
    cin >>T;
    vector <int> ans;
    for(int k=0;k<T;k++){
        int n;
        cin >>n;
        vector <int> a(n+1,0);
        vector <int> b(n+1,0);
        
        for(int i=0;i<n;i++){
            int tmp;
            cin >>tmp;
            a[i]=tmp;
        }
        
        for(int i=0;i<n;i++){
            int tmp;
            cin >>tmp;
            b[i]=tmp;
        }
        
        if(n>=3){
            
            a[1]+=b[0];
            b[1]+=a[0];
            for(int i=2;i<n;i+=2){
            a[i]=max(a[i]+b[i-2],a[i]+a[i-2]+b[i-1]);    
            b[i]=max(b[i]+a[i-2],b[i]+b[i-2]+a[i-1]);
            }
        
            if(n%2==0)
                    ans.push_back(max(a[n-2]+b[n-1],b[n-2]+a[n-1]));
            else
                    ans.push_back(max(a[n-1],b[n-1]));
                
        }
        else
            ans.push_back(max(a[0]+b[1],b[0]+a[1]));
        
    }
    
    for(int i=0;i<T;i++){
        cout<<ans[i]<<'\n';
    }
    
    return 0;
}

▲ in-place로 짠 아직 미완성인 코드 좀 더 고민해봐야겠다...

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; 
 
int main(){
    int T;
    cin >>T;
    vector <int> ans;
    for(int k=0;k<T;k++){
        int n;
        cin >>n;
        vector <int> a(n+1,0);
        vector <int> b(n+1,0);
        vector <int> ansa(n+1,0);
        vector <int> ansb(n+1,0);
        
        for(int i=0;i<n;i++){
            int tmp;
            cin >>tmp;
            a[i]=tmp;
        }
        
        for(int i=0;i<n;i++){
            int tmp;
            cin >>tmp;
            b[i]=tmp;
        }
        
        if(n==1)
            cout<<max(a[0],b[0])<<'\n';
        else if(n==2)
            cout<<max(a[0]+b[1],b[0]+a[1])<<'\n';
        else{
            
            ansa[0]=a[0]; ansb[0]=b[0];
            ansa[1]=b[0]+a[1]; ansb[1]=a[0]+b[1];
                        
            for(int i=2;i<n;i++){
            ansa[i]=max(a[i]+ansb[i-1],a[i]+ansb[i-2]);    
            ansb[i]=max(b[i]+ansa[i-1],b[i]+ansa[i-2]);
            }
            
            cout<<max(ansa[n-1],ansb[n-1])<<'\n';
        }
    
    }
    
    return 0;
}

 

스티커의 열을 받고 배열을 만든 후에 스티커 점수입력을 받고 나서 스티커의 열이 1개라면 그냥 2행의 점수중에 큰 점수가 최대값이 되므로 출력하고 2개라면 대각선으로 이어진 경우의 수가 2개 나오므로 그중 큰 경우의 수를 출력하며 3개 이상일 경우 DP문제이므로 sub문제들의 답을 계산해서 최종 답을 구하는 방법을 사용하였다. 

위의 답과 다른 분들의 코드를 비교해보니 Max는 algorithm을 쓰지않고 그냥 삼항 연산자로 구현할 수 있다는 것, vector를 쓰지않고 그냥 배열로도 사용할 수 있다는 것이 차이점이었다. C++,C의 차이라고 할 수 있겠다.