[백준 30460] 스위치 (C++)

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

문제

---

 i초에 A_i의 점수를 얻는 게임이 있다. N초 동안 진행하는 이 게임에서는 점수를 추가로 얻기 위해 T초에 스위치를 눌러 T,T+1,T+2초에 얻는 점수를 2배로 만들 수 있다. T초에 스위치를 누르면 T+3초부터 다시 스위치를 누를 수 있다.

게임이 진행되는 동안 스위치를 적절하게 눌렀을 때 얻을 수 있는 점수의 최댓값을 구해보자.

입력

---

첫째 줄에 점수를 얻는 횟수 N이 주어진다. (3 ≤ N ≤ 200,000) 

둘째 줄에 i초에 얻는 점수를 나타내는 정수 A_i가 공백으로 구분되어 주어진다. (1 ≤ i ≤ N; |A_i|≤1000)

출력

---

얻을 수 있는 점수의 최댓값을 출력한다.

 

문제 풀이

---

dp 문제.

i번째 인덱스에서 나올 수 있는 경우의 수는 스위치가 눌리지 않았을 때, 스위치를 누른지 0초 되었을 때, 스위치를 누른지 1초 되었을 때, 스위치를 누른지 3초 되었을 때 총 4가지의 경우가 있다. 이 네 가지의 경우를 나누어 가장 큰 점수를 저장한 배열을 채운 후 N-1번째 index에서 네 가지의 경우 중 가장 큰 점수를 출력한다.

 

i초에 얻는 점수를 나타내는 배열을 arr, 가장 큰 점수를 저장하는 배열을 dp라 가정한다.

i번째에서 스위치가 눌리지 않았다면 i-1번째에서 스위치가 눌리지 않았거나, i-1번째가 스위치를 누른지 2초째 되었고 i번째에서 스위치를 누르지 않은 상태이다.따라서 dp[i][0] = max(dp[i-1][0], dp[i-1][2])+arr[i]가 성립한다.

i번째에서 스위치를 누른지 0초 되었다면 i-1번째에서 스위치가 눌리지 않은 상태이거나, i-1번째가 스위치를 누른지 2초째 되었고 i번째에서 스위치를 누른 상태이다. 따라서 dp[i][1] = max(dp[i-1][0], dp[i-1][2])+2*arr[i]가 성립한다.

i번째에서 스위치를 누른지 1초 되었다면 i-1번째에서 스위치를 누른 것이다. 따라서 dp[i][2]=dp[i-1][1]+2*arr[i]가 성립한다.

i번째에서 스위치를 누른지 2초되었다면 i-2번째에서 스위치를 누른 것이고, i-1번째에서는 스위치가 눌러진 지 1초 된 것이다. 따라서 dp[i][3]=dp[i-1][2]+2*arr[i]가 성립한다.

[N-1][0], [N-1][1], [N-1][2], [N-1][3] 중 가장 큰 값을 구해 출력하면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* arr = new int[N];
	long long** dp = new long long*[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		dp[i] = new long long[4];
		for (int j = 0; j < 4; j++)
		{
			dp[i][j] = -200000000;
		}
	}
	dp[0][0] = arr[0];
	dp[0][1] = 2 * arr[0];
	for (int i = 1; i < N; i++)
	{
		dp[i][0] = max(dp[i - 1][0], dp[i-1][3]) + arr[i];
		dp[i][1] = max(dp[i - 1][0], dp[i-1][3]) + 2 * arr[i];
		dp[i][2] = dp[i - 1][1] + 2 * arr[i];
		dp[i][3] = dp[i - 1][2] + 2 * arr[i];
	}
	cout << max({ dp[N - 1][0], dp[N - 1][1], dp[N - 1][2], dp[N - 1][3] })<<"\n";
	return 0;
}