[프로그래머스] 스티커 모으기(2)

링크

https://programmers.co.kr/learn/courses/30/lessons/12971

코딩테스트 연습 - 스티커 모으기(2) | 프로그래머스

풀이

스티커가 원형으로 연결이 되어 있고, 하나의 스티커를 떼면 양 옆의 스티커를 사용할 수 없다.

 

이때 원형으로 연결된 스티커를 한 줄로 나열을 해보았을 때

14 6 5 11 3 9 2 10으로 나열할 수 있고

 

11 스티커를 사용하였을 때 사용할 수 있는 스티커는 6과 14 스티커를 이용할 수 있다.

이를 통해 점화식을 도출할 수 있는데 dp [i] = sticker [i] + max(dp [i-2], dp [i-3])이라는 식을 구할 수 있다.

 

하지만 14 스티커를 사용하였을 때 10 스티커를 동시에 사용할 수 없다.

 

그래서 두 가지 조건으로 나누었는데

1. 14 스티커를 사용하고 10 스티커를 사용하지 않았을 때

2. 14 스티커를 사용하지 않고 10 스티커를 사용하였을 때

 

이렇게 나누어 dp배열을 채우고 dp배열 탐색을 통하여 가장 큰 원소의 합을 찾았다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>

#define SIZE 101000

using namespace std;

typedef long long int ll;

const int INF = 2000000000;

int arr[SIZE];
int dp[SIZE];

int solution(vector<int> sticker)
{
	int s_size = sticker.size();
	int res = 0;
	for (int i = 0; i < s_size; i++) {
		arr[i + 1] = sticker[i];
	}
	//첫번째 쓰고 마지막 안썻을때
	dp[1] = arr[1];
	dp[2] = arr[2];

	res = max(res, max(dp[1], dp[2]));
	for (int i = 3; i < s_size; i++) {
		dp[i] = arr[i] + max(dp[i - 2], dp[i - 3]);
		res = max(res, dp[i]);
	}

	//첫번째 안쓰고 마지막 썻을때
	dp[1] = 0;
	dp[2] = arr[2];

	for (int i = 3; i <= s_size; i++) {
		dp[i] = arr[i] + max(dp[i - 2], dp[i - 3]);
		res = max(res, dp[i]);
	}

	return res;
}