[C++/27210] 신을 모시는 사당

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

천천히 문제를 그려나가보니, 입력값도 작고(N = 100,000) 두방향(1인지 2인지) 판단을 해보면서 어느 범위가 가장 많은 값을 얻을 수 있을 것인가 생각해보는 문제라고 생각한다. 그렇게 어려운 방법은 아닌데, 아마 새로운 방법이 있지 않을까 생각이 됩니다. 

정리하자면, 1을 기준으로 차례로 금을 칠하면서 어느 범위까지 값이 가장 큰지 차례대로 dp[i-1]과 현재 값을 비교하면서 최고의 깨달음과 2를 기준으로 위의 내용과 같이 진행해서, 그 두개의 dp 테이블에서 가장 큰 값을 구하면 됩니다.

아래는 정답 코드입니다.

#include<iostream>
#include<cstring>

#define MAX 100000
using namespace std;

int n,answer,board[MAX],dp[MAX];

void init() {
	answer = -987654321;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> board[i];
}

//void printDp() {
//	
//	cout << "print array!" << "\n";
//	
//	for(int i = 0; i < n; i++){
//		cout << dp[i] << " ";
//	}
//	cout < "\n";
//	
//}

int maxCount() {
	
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans = max(dp[i], ans);
	}
	
	return ans;
}

int main() {
	
	init();
	
	for(int i = 0; i < n; i++){
		int score = board[i] == 1 ? 1 : -1;
		
		if(i == 0){
			dp[i] = score;
		} else{
			dp[i] = max(dp[i - 1] + score, score);
		}
	}
	
	answer = max(maxCount(),answer);
	memset(dp,0,sizeof(dp));
	
	for(int i = 0; i < n; i++){
		int score = board[i] == 2 ? 1 : -1;
		
		if(i == 0){
			dp[i] = score;
		} else{
			dp[i] = max(dp[i - 1] + score, score);
		}
	}
	
	answer = max(maxCount(), answer);
	cout << answer;
	
	return 0;
}