9465번 스티커_다시 풀어야 함.

phoenixKim·2022년 8월 27일
0

백준 알고리즘

목록 보기
86/174

최종 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <map>
#include <cstring>

// 9465번. 스티커 
// 16:29 ~ 

int dp[100001][3];
int v[100001][2];

int main()
{
	// n이 20만임. 
	// 40만의 탐색 시간이 걸리므로. 
	// 다른 효율적인 방법을 찾아야 함. 


	// 총 2가지의 경우의 수가 있음. 
	// 열의 갯수, 스티커를 어떻게 처리할 것인가? 
	// 위쪽 스티커 뜯기 , 아래쪽 스티커 뜯기

	// 위쪽 뜯으면 0
	// 아래 뜯으면 1
	// 안뜯으면 2

	// 위쪽스티커를 뜯을 경우,
	// dp[n][0] = max(  dp[n - 1][1] , dp[n - 1][2]  ) + v[n][0]
	
	// 아래쪽 스티커 뜯을 경우.
	// dp[n][1] = max( dp[n - 1][0] , dp[n - 1][2] ) + v[n][1] 

	// 스티커를 안 뜯으면? 
	// 0이 아닐까 생각할 수 있는데... 
	// 위쪽과 아래쪽에 영향을 주기 위해서, 뭔가 작성을 해야함.
	// dp[n][2] = max(dp[n - 1][0]  , dp[n - 1][1] , dp[n - 1][2]);

	int t, n;
	cin >> t;

	for (int i = 0; i < t; ++i)
	{
		cin >> n;

		//vector<vector<int>>v(2, vector<int>(n));

		for (int j = 0; j < n; j++) {
			cin >> v[j][0];
		}
		for (int j = 0; j < n; j++) {
			cin >> v[j][1];
		}
		memset(dp, -1, sizeof(dp));

		dp[0][0] = dp[0][1] = dp[0][2] = 0;

		for (int a = 1; a <= n; ++a)
		{
			dp[a][0] = max(dp[a - 1][1], dp[a - 1][2]) + v[a - 1][0];
			dp[a][1] = max(dp[a - 1][0], dp[a - 1][2]) + v[a - 1][1];
			dp[a][2] = max({ dp[a - 1][0], dp[a - 1][1], dp[n - 1][2] });
		}

		cout << max({ dp[n][0], dp[n][1], dp[n][2] }) << "\n";

		// max 3개 이상 원소 비교할 때는 {} 중괄호 붙여야 함.
	}

}

첫번째 풀이 전략

  • [0][0] 부터 시작해서 지그재그로 진행하면서 누적
  • [1][0] 부터 시작해서 지그재그로 진행하면서 누적
  • [0][0] 부터 시작해서 지그재그로 진행하다가 n - 2에서
    max(v[n -1][0] , v[n -1][1]) 가산하는 방법
  • [1][0] 부터 시작해서 지그재그로 진행하다가 n - 2에서
    max(v[n -1][0] , v[n -1][1]) 가산하는 방법

=> 예제는 맞지만, 틀림으로 나옴...

마인드셋

틀렸지만, 정신을 부여잡고, 점화식을 다시 한번 만들어보는 시도를 해야함.
코딩테스트에서 이럴 경우 어쩔겨!
반례를 찾기에는 0%에서 틀렸으니까 다시 만들어보자.

  • pdf 파일을 보니까, 해당 열을 뜯지 않을 경우, 해당 열에서 첫번째 행을 뜯을 경우, 해당 열에서 두번째 행을 뜯을 경우에 대한
    3가지 경우의 수로 나뉘어서 dp를 만들고 , 최대값을 구하고 있음.

완료는 하지 않았지만, 해설

n번째 열까지 진행하고 + 뜯고, 위쪽 뜯어? 아래쪽 뜯어 총 3번의 경우의 수를 가지므로 점화식은 이렇게 나타낼 수 있음.
dp[i][3] : i번 열에서 스티커를 안뜯어, 위쪽 뜯어, 아래쪽 뜯었을 때의 최대값

0 : 안 뜯어
dp[i][0] : max(dp[i - 1][0] , dp[i -1][1] , dp[i - 1][2]); 이런식으로.
1 : 위쪽 뜯어
dp[i][1] : max(dp[i -1][0] ,dp[i -1][2] ) + 현재 인덱스의 위쪽부분 원소
//=> 이런식으로...

profile
🔥🔥🔥

0개의 댓글

관련 채용 정보