# 카드 선택

# 문제

# 입력 및 출력

# 풀이

입력 예를 dp로 풀어보았다.

처음에는 1차원 dp를 썼는데 조건문이 너무 들어가는데다가 너무 어려워져서 다른 방법을 생각했다.

그래서 i-4를 선택하는 경우, i-3을 선택하는 경우, i-2를 선택하는 경우로 나눠서 풀었다.

i번째 카드를 선택하고 이전에 선택한 카드가 i-4번째 카드인 경우, i-3번째 카드인 경우, i-2번째 카드인 경우 중에서

가장 큰 것을 선택해서 푸는 방법이다.

편의를 위해 인덱스의 0번은 전부 사용하지 않았다.

그래서 인덱스 1번부터 3번까지는 이전에 선택할 카드가 따로 없기 때문에 dp에 a[i]만 그대로 넣어준다.

인덱스가 4번일땐 i-4번째 카드는 선택할 수 없기 때문에 INF 값을 넣어줘서 max 비교 시 문제가 없도록 설정해줬다.

처음에 풀었을 땐 문제가 없는 줄 알았는데

두 번째 예제를 풀면서 문제가 발생했다.

i-2가 두번 연속으로 선택되면 i-4, i-2가 선택되는 경우가 된다.

이렇게 되면 조건 3번을 만족하지 않기 때문에

dp[3]에선 이전에 카드를 선택할 때 i-2를 선택하는 경우를 제외해준다.

다시 정리하면 dp[3]은 i번째 카드를 선택하고 이전엔 i-2번째 카드를 선택하는 경우이기 때문에

dp테이블의 3행에서만 i-2번째 카드를 연속으로 선택하는 경우를 제외해주면 된다.

#include <fstream>
#include <algorithm>
#define INF -987654321
using namespace std;

ifstream fin("card.inp");
ofstream fout("card.out");

int a[1001], dp[4][1001]; // index 0 isn't use

int main() {
	int T, n;
	fin >> T;
	while (T--) {
		fin >> n;
		for (int i = 1; i <= n; i++) {
			fin >> a[i];
		}
		for (int i = 1; i <= 3; i++) {
			dp[i][1] = a[1];
			dp[i][2] = a[2];
			dp[i][3] = a[3];
		}
		dp[1][4] = INF, dp[2][4] = a[1] + a[4], dp[3][4] = a[2] + a[4];
		for (int i = 5; i <= n; i++) {
			dp[1][i] = a[i] + max({ dp[1][i - 4],dp[2][i - 4],dp[3][i - 4] });
			dp[2][i] = a[i] + max({ dp[1][i - 3],dp[2][i - 3],dp[3][i - 3] });
			dp[3][i] = a[i] + max({ dp[1][i - 2],dp[2][i - 2] });
			// Selecting n-2 twice in a row does not satisfy condition 3.
		}
		fout << max({ dp[1][n],dp[2][n],dp[3][n] }) << "\n";
	}
}

주석은 espa에 돌릴때 문제가 날까봐 영어로 적어놨다ㅋㅋ

전에 운영체제 할 땐 한글 주석이 오류가 났어서,,