[BOJ 24498] 백준 24498번 - blobnom

		제 1회 블롭컵 풀이
A		[BOJ 24498] blobnom
B		[BOJ 24499] blobyum
C		[BOJ 24500] blobblush

1. 문제

$24498$. blobnom (제1회 블롭컵 A번)

백준 24498번 - blobnom (https://www.acmicpc.net/problem/24498)

2. 풀이

$N<=1,000,000$에 시간 초과가 $1$초이므로, $O(nlogn)$이나 $O(n)$ 문제인데, 이분탐색과 같은 것을 사용할만한 문제가 아니므로 그리디 문제라고 볼 수 있다.

$1\rightarrow 2\rightarrow 3$ 작업을 거치게 되면, 최종 블롭의 개수가 $1$이 감소한다는 사실이 중요하다. 만들 수 있는 가장 높은 탑 즉, 결과값을 갖게 되는 탑의 위치가 하나 정해져 있다고 가정한다.

이때, 이 탑의 높이를 높이는 작업이 아닌 다른 작업을 하는 경우, 어떤 식으로든 전체의 블롭 개수가 감소하게 되어, 최종적으로 결과값을 갖게 되는 탑의 높이를 최대화하는데 손해를 일으킨다.

따라서, 가장 높은 탑의 높이를 갖게 되는 위치를 정했다면, 그 위치의 탑의 높이를 높이는 작업만 수행되어야 한다. 이는 $1\rightarrow 2\rightarrow3$의 작업을 해당 탑만 선택해서 가능할 때까지 수행하는 것을 의미한다. (다른 작업은 일체 하지 않아야 한다.)

최종 위치는 $1$부터 $N$까지 어디든지 될 수 있다. 최종 위치 양끝에서 블롭을 뺄 수 있는 만큼 빼서 최종 위치에 쌓는다. (단, $1$과 $N$에서는 인접한 탑이 하나 없으므로 이 작업이 불가능하다.) 즉, 양쪽의 최솟값이 쌓아 올릴 수 있는 개수의 최댓값이다.

이렇게 만들어진 값들의 최댓값을 구한다. 또한, 작업을 $0$번 수행할 수 있으므로, 초기 탑의 높이들도 최댓값을 갱신하는 요소 중 하나이다. ($1$과 $N$의 초기 높이는 이때 검사된다.)

3. 채점 결과

4. 회고

초기 높이를 최댓값을 갱신하는데 사용하지 않아 이를 간과하여 WA를 받았다.

5. 코드