쌓고 쌓다
[백준] 창고 다각형 2304번 C++ 풀이 본문
https://www.acmicpc.net/problem/2304
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int max_pos, max_h; // 최대 높이의 위치와 높이
int arr[1001];
int res = 0
int main(void)
{
int L, H;
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> L >> H;
arr[L] = H;
if (max_h < H)
{
max_pos = L;
max_h = H;
}
}
int Lh=0; // 왼쪽 영역의 최고 높이
for (int i = 1; i <max_pos; i++)
{
Lh = max(Lh, arr[i]);
res += Lh;
}
int Rh=0; // 오른쪽 영역의 최고 높이
for (int i = 1000; i > max_pos; i--)
{
Rh = max(Rh, arr[i]);
res += Rh;
}
cout << res + max_h;
}
위 그림처럼 최대 높이의 인덱스를 기준으로 왼쪽 영역과 오른쪽 영역의 넓이를 구하면 됩니다.
왼쪽 영역은 0부터 시작해 최대 높이의 인덱스 전까지 매 인덱스마다 현재까지의 최대 높이를 더해주고
매 인덱스 탐색마다 현재까지의 최대 높이가 더 높아질 경우 갱신해주면 됩니다.
마찬가지로 오른쪽 영역의 넓이를 구하고
그 결과에 최대 높이를 더해주면 됩니다.
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 생태학 4358번 C++ 풀이 (0) | 2022.01.03 |
---|---|
[백준] 공장 7578번 C++ 풀이 (0) | 2022.01.02 |
[백준] 대칭 차집합 1269번 C++ 풀이 (0) | 2021.12.31 |
[백준] 카드 합체 놀이 15903번 C++ 풀이 (0) | 2021.12.30 |
[백준] 최솟값 찾기 11003번 C++ 풀이 (0) | 2021.12.29 |
Comments