[DP] 백준 문제 풀이 - 9465 스티커

👩🏻‍💻 문제링크

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

9465번: 스티커

 

✍️ 아이디어

1. 문제 이해

• 동물원과 비슷한 문제임 스티커를 뜯는데 인접한 곳의 스티커는 못씀

2.  D[N][2] = 2행 N열의 스티커로 얻을수 있는 최대 정수 (0인경우 위에 스티커 사용, 1인경우 아래 스티커 사용, 2인경우 N열 스티커 사용 안함)

3. 처음에 스티커 사용 안하는것에 구현을 애먹었는데 그냥 이전 result에서 max 구하면 되는거였음

 

4. 나중에 깨달은 것인데 건너뛰는 경우에서는 무조건 이런 경우임 대각선으로 있는 경우

0
	여기에 o못오니까	0

 

✍️소스코드

• 삽질 하다가 강의 듣고 깨달음 (내 풀이)

#include <iostream>
#include <algorithm>
using namespace std;
long long result[100001][3];
int score[100001][2];
int main()
{
	int t; cin>>t;
	
	for(int i=0; i<t; i++)
	{
		int n; cin>>n;
		for(int j=0; j<=1; j++)
		{
			for(int k=1; k<=n; k++)
			{
				cin>>score[k][j];
			}
		}
		result[1][0]=score[1][0];
		result[1][1]=score[1][1];
		result[1][2]=0;
		for(int j=2; j<=n; j++)
		{
			result[j][0]=max(result[j-1][1], result[j-1][2])+score[j][0];
			result[j][1]=max(result[j-1][0], result[j-1][2])+score[j][1];
			result[j][2]=max(result[j-1][0],max(result[j-1][1], result[j-1][2]));
            //[j][2] 부분을 되게 복잡하게 구현했었음..
		}
		cout<<max(result[n][0],max(result[n][1],result[n][2]))<<'\n';
	}
}

 

• 다른사람의 풀이 (건너 뛰는 경우를 중점으로 코드를 짠듯)
•  dp[0][i] = buf[0][i] + dp[1][i - 2]; 인 경우는 i-1열을 건너뛴 경우이다

#include <iostream>
#include <cstdio>
 
using namespace std;
 
const int MAXN = 100000;
 
int buf[2][MAXN + 1] = { 0, };
int dp[2][MAXN + 1] = { 0, };
 
int max(int a, int b) { if (a > b) return a; return b; }
 
int bottomUp(int n) {
    for (int i = 0; i < n; i++) 
        scanf("%d", &buf[0][i]);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &buf[1][i]);
 
    dp[0][0] = buf[0][0];
    dp[1][0] = buf[1][0];
    dp[0][1] = buf[0][1] + dp[1][0];
    dp[1][1] = buf[1][1] + dp[0][0];
 
    for (int i = 2; i < n; i++) {
        dp[0][i] = buf[0][i] + max(dp[1][i - 1], dp[1][i - 2]); //[1][i-2]인 경우는 건너뛴 경우
        dp[1][i] = buf[1][i] + max(dp[0][i - 1], dp[0][i - 2]); //[0][i-2]인 경우는 건너뛴 경우
    }
 
    return max(dp[0][n - 1], dp[1][n - 1]);
}
 
int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d\n", bottomUp(n));
    }
    return 0;
}

체감난이도	걸린시간	참고	사용 문법
상	1hour	강의	이차원 DP