취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24498번 문제인 blobnom이다.

문제는 아래 링크를 확인하자.

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

각 위치마다 세울 수 있는 가장 큰 탑의 높이를 생각해보자.

먼저, 양 끝의 탑의 경우 아무런 연산을 못 하므로 그 자체가 가능한 가장 큰 탑의 높이이다.

양 끝의 탑이 아닌 탑 K의 경우, 그 옆의 탑에 아무리 먼저 연산을 하더라도 그 탑의 높이 증가량과 K의 높이 감소량이 일치하기 때문에 옆의 탑에 연산을 하는 것으로 이득을 볼 수 없다는 것을 관찰하자. 따라서 K의 위치에서 연산을 가능한 한 많이 진행하는 것으로 해당 위치의 탑의 최대 높이를 알아낼 수 있다.

위의 내용을 이용하여 가능한 탑의 높이의 최댓값을 알아내자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[1000000];

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	int ans = max(arr[0], arr[N - 1]);
	N--;
	for (int i = 1; i < N; i++) ans = max(ans, arr[i] + min(arr[i - 1], arr[i + 1]));

	cout << ans;
}