본문 바로가기

알고리즘

백준 9465 번 - 스티커 (C++/DP/Dynamic Programming)

728x90
반응형

문제

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

 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

 

접근법

전형적인 DP문제 라지만 내가 지금까지 풀어왔던거와 살짝 달라서 매우 헤매다, 검색해서 힌트를 얻고 풀었다.

스티커의 값을 구하는데 규칙이 없어보이지만, 스티커는 1칸 대각선, 2칸 대각선으로만 이동할 수 있다. (양 옆이 인접한 곳으로는 이동하지 못하므로).

3칸 대각선 (1칸 대각선을 3번 이동한게 무조건 더 크다) 부터는 다른 값을 거쳐갈 수 있어서 불가능 하다.

이를 이용해 dp를 사용하며,

(1칸 대각선, 2칸 대각선) -> 여기선 cache[0][i-1], cache[0][i-2] 중 큰 값을 구해서(이전에 계산된 최대값) stickers[1][i-1]을 더해주면 된다.(대각선에 위치한 값

 

cache와 stickers의 위치가 달라서 조금 햇갈렸다.

접근법만 알면 쉽게 풀 수 있는 문제인 것 같다. 좀 더 많은 문제를 풀어보며 경험을 쌓아야겠다.

코드

#include <iostream>
#include <vector>

using namespace std;

int cache[2][100001] = { 0, };

int main()
{
	cin.tie(0);
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) 
	{
		int nums;
		cin >> nums;
		vector<vector<int>> stickers(2, vector<int>(nums));
		for (int k = 0; k < 2; k++) {
			for (int j = 0; j < nums; j++)
			{
				int M;
				cin >> M;
				stickers[k][j] = M;
			}
		}
		// 입력 끝 코드작성
		/*
		*	50 10 100 20 40
			30 50  70 10 60
			경우의수는 한칸 대각선 , 두 칸 대각선밖에 없다. 두칸으로 오른쪽간다 생각해보면 대각선으로 거쳐가는게 "무조건"크다
		*/
		int ans = 0;
		cache[0][0] = cache[1][0] = 0;
		cache[0][1] = stickers[0][0]; cache[1][1] = stickers[1][0];
		for (int j = 2; j <= nums ; j++)
		{
			cache[1][j] = std::max(cache[0][j - 1], cache[0][j - 2]) + stickers[1][j - 1];
			cache[0][j] = std::max(cache[1][j - 1], cache[1][j - 2]) + stickers[0][j - 1];
		}
		cout << std::max(cache[0][nums], cache[1][nums]) << "\n";
	}
}
반응형