[Kick Start][Practice Round 2019] Mural :: seoftware

문제 이해

N개의 구간으로 나뉘어진 벽에 벽화를 칠한다. 매일 아침 하나씩 칠하고, 다음날은 전날 칠한 벽화의 양 옆 중 하나를 칠 할 수 있다. 매일 저녁에는 맨 끝에 있는 벽 두 개 중에 하나는 못쓰게 된다(단, 이미 칠한 벽화는 지워지지 않는다). 각 벽에는 beauty score가 있는데 내가 칠할 수 있는 벽화 중 가장 높은 beauty score를 갖는 case를 찾으면 된다.

위에가 문제고 이것을 풀이하기 위해 다가간다면, 두가지 중요한 포인트가 있다.

1. 매일 한 구역은 벽화가 칠해지고, 한 구역은 사용할 수 없게 된다. 따라서 최대로 칠할 수 있는 벽화의 개수는 [N/2]개이다. 

2. 이미 그려진 벽화의 양 옆에만 그릴 수 있으므로 선택되는 벽 [N/2]개는 연속적이다.

따라서, 부분합이 가장 큰 부분을 찾는 것이 이 문제의 핵심이다.

소스코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main(void) {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		int N;
		cin >> N;
		vector<int> beauty_score(N, 0);
		for (int n = 0; n < N; n++) {
			scanf_s("%1d", &beauty_score[n]);
		}
		int total_painted = (N + 1) / 2;
		
		long long int tmp = 0;
		//초기값
		for (int i = 0; i < total_painted; i++) {
			tmp += beauty_score[i];
		}
		long long int y = tmp; //answer
		//맨 앞에꺼 빼고 다음꺼 더하기
		for (int i = 0; i < N - total_painted; i++) {
			tmp = tmp - beauty_score[i] + beauty_score[i + total_painted];
			if (tmp > y) y = tmp;
		}

		//output
		cout << "Case #" << t << ": " << y << endl;
	}
}

결과

처음에는 다 더했는데 시간초과로 실패하고, 위의 방법으로 다시했다.. 5번의 시도끝에 통과!