[백준] 20033번 : Square, Not Rectangle (C++)

20033번 : Square, Not Rectangle

---

 

문제)

A histogram is a polygon made by aligning N adjacent rectangles that share a common base line. Each rectangle is called a bar. The i-th bar from the left has width 1 and height H_i.

Your goal is to find the area of the largest rectangle contained in the given histogram, such that one of the sides is parallel to the base line.

 

 

Actually, no, you have to find the largest square. Since the area of a square is determined by its side length, you are required to output the side length instead of the area.

 

 

 

 

 

입력 :

On the first line, a single integer N is given, where 1≤ N ≤300000

On the next line, N space-separated integers 1,2,⋯,H_1, H_2, ..... , H_N, are given. H_i (1≤ H_i ≤10^9) is the height of the i-th bar. 

 

 

 

출력 :

Output the side length of the largest square in the histogram, such that one of the sides is parallel to the base line.

 

 

 

 

 

 

풀이)

 

// 20033. 
#include <iostream>
#include <vector>
#include <limits.h>
 
using namespace std;
 
int n;
vector<long long> vec;
 
// x의 크기의 정사각형이 만들어질 수 있을까?
bool check(long long x)
{
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        // x크기보다 작은 막대가 나온다면 초기화
        if (vec[i] < x) cnt = 0;
        else 
        {
            cnt++;
            if (cnt >= x) return true;
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vec.resize(n);
    for (long long& ele : vec) cin >> ele;
 
 
    long long s = 0;
    long long e = INT_MAX;
    
    long long ans = 0;
    while (s <= e)
    {
        long long mid = (s + e) / 2;
 
        // mid의 크기로 해당 크기의 정사각형이 만들어질 수 있는지
        // 확인
        if (check(mid))
        {
            ans = mid;
            s = mid + 1;
        }
        else e = mid - 1;
    }
 
    cout << ans;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/20033 

20033번: Square, Not Rectangle