백준 - 9465 스티커

문제

https://www.acmicpc.net/problem/9465

9465번: 스티커

서로 붙어있지 않은 스티커를 골라 가장 높은 점수를 구하는 문제였다.

 

문제 풀이

N이 100000이라 완전탐색으로 풀면 시간 초과가 날 것 같아서 dp로 풀었다.

 

처음에 예시만 보고 점화식을 만들어 풀었더니 틀렸다고 나와서 반례를 찾아 점화식을 수정했다.

0 : 50
1 : 100 50+50 vs 10 -> 100
2 : 200 100+100 vs 50+70 -> 200
3 : 210 200+10 vs 100+20 -> 210
4 : 260 210+40 vs 200+60 -> 260

0: 20
1: 50 10+40 vs 20+30 -> 50
2: 80 50+10 vs 50+30 vs 20+30 -> 80
3: 130 80+50 vs 50+50 -> 130
4: 190 130+60 vs 80+100 -> 190
5: 210 190+20 vs 130+20 -> 210
6: 290 210+80 vs 190+80 -> 290

반례 예시
10 40 70 80 90 150
50 20 80 160 20 10 430

 

처음 풀이 (틀린 풀이)

처음에는 vector<pair<int,int>> 형태의 dp를 만들었다. pair의 first에는 점수를, second에는 현재 선택한 스티커의 위치를 넣어줬다. 0이면 위, 1이면 아래, 2면 둘 다 가능한 경우였다.

 

점화식은 [ 전꺼+안붙어있는 현재꺼 / 전전꺼+현재 max ] 로 짰고, 만일 전꺼가 위아래 둘 다 가능(같은경우)한 경우에는 3개를 비교해 줬다.

 

하지만 이렇게 하니 위의 마지막 반례가 해결되지 않았다.

 

두 번째 풀이 (맞은 풀이)

dp도 sticker처럼 똑같은 형태로 만들어 현재 위치에서 가장 큰 sum 값을 저장하도록 했다. 

위(dp[0][]) : 전아래+현재위 전전위+현재위 전전아래+현재위
아래(dp[1][]) : 전위+현재아래 전전위+현재아래 전전아래+현재아래

 

해당 점화식으로 진행했고 훨씬 직관적이고 깔끔하게 풀 수 있었다.

 

dp는 너무,, 싫,,,다,,, 점화식 생각하는게 맨날 달라서,,,열심히 풀어야지.....

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	for(test_case = 1; test_case <= T; ++test_case)
	{
        int N;
        scanf("%d",&N);
        vector<vector<int>> sticker(2, vector<int>(N)); 
        //dp : 현재 위치에서 가장 큰 값
        vector<vector<int>> dp(2, vector<int> (N, 0));

        for(int i=0;i<2;i++){
            for(int j=0;j<N;j++){
                scanf("%d",&sticker[i][j]);
            }
        }
        
        dp[0][0] = sticker[0][0];
        dp[1][0] = sticker[1][0];
        if(N == 1) {            
            printf("%d\n",max(dp[0][0], dp[1][0]));
            continue;
        }
        dp[0][1] = dp[1][0]+sticker[0][1];
        dp[1][1] = dp[0][0]+sticker[1][1];
        
        for(int i=2;i<N;i++){  
            //위 : 전아래+현재위  전전위+현재위  전전아래+현재위
            //아래 : 전위+현재아래  전전위+현재아래  전전아래+현재아래
            //위
            int beforeMax = max(dp[0][i-2]+sticker[0][i], dp[1][i-2]+sticker[0][i]);
            dp[0][i] = max(dp[1][i-1]+sticker[0][i], beforeMax);

            //아래
            beforeMax = max(dp[1][i-2]+sticker[1][i], dp[0][i-2]+sticker[1][i]);
            dp[1][i] = max(dp[0][i-1]+sticker[1][i], beforeMax);

        }
        
        printf("%d\n",max(dp[0][N-1], dp[1][N-1]));                
	}
	return 0;
}