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

1. 문제Permalink

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

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

2. 풀이Permalink

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

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

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

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

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

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

3. 채점 결과Permalink

boj-24498

4. 회고Permalink

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

5. 코드Permalink

#include <bits/stdc++.h>
using namespace std;
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long int
#define pii pair<int, int>
#define PQ priority_queue
#define LEN(v) int(v.size())
#define ALL(v) v.begin(),v.end()
#define INF 2e9
#define LINF 1e18
int main() {
FASTIO;
int N;
cin >> N;
vector<ll> A(N);
ll maxi = 0;
FOR(i, 0, N - 1) {
cin >> A[i];
maxi = max(maxi, A[i]);
}
FOR(i, 1, N - 2) {
maxi = max(maxi, A[i] + min(A[i - 1], A[i + 1]));
}
cout << maxi;
return 0;
}

댓글남기기