C++ / 백준 / 24498 / blobnom

문제

 

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

24498번: blobnom

 

 

문제풀이

 

맨 처음과 맨 끝을 제외한 탑에 있는 블롭의 수 + 인접한 두 타워 중 블롭의 최솟값을 더한 값 중 최댓값을 구하는 문제이다.

조심할 점은 인접한 블롭수를 더하지 않는 맨 처음 또는 맨 끝에 있는 탑의 블롭수가 정답일 수도 있다는 점이다.

 

먼저 answer에 맨 처음 타워인 tower[0], 맨 끝 타워인 tower.back() 중 최댓값을 저장해 놓는다.

 

그다음 1부터 N-2까지 탐색하면서 해당 타워의 인접한 두 타워 블롭 수의 최솟값 + 해당 타워의 블롭수 중 최댓값을 answer에 저장하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

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

	int N(0);
	cin >> N;
	vector<int>tower(N, 0);
	for (int idx = 0; idx < N; ++idx) cin >> tower[idx];

	int answer(max(tower[0],tower.back()));	

	for (int idx = 1; idx + 1 < N; ++idx) {
		answer = max(answer, tower[idx] + min(tower[idx - 1], tower[idx + 1]));
	}
	cout << answer;
}