[SWA] 1206. view

1206. view

조망권이 보장된 가구의 수를 구하는 문제이다.

해당 가구의 좌우로 두칸이 비워져 있어야 조망권이 보장된다고 한다.

주어지는 것은 아파트의 높이 뿐이다.

문제 해결 전략

우선 왼쪽에서 두칸 중 더 큰 아파트의 높이를 구한다.

그리고 나서 오른쪽에서 두칸 중 더 큰 아파트의 높이를 구한다.

그리고 두 아파트의 높이 중 더 큰 아파트의 높이를 구한다.

현재 아파트의 높이에서 위에서 구한 아파트의 높이를 빼면 조망권이 보장된 가구 수를 구할 수 있다.

위 처럼 하는 이유는 좌우 네 채의 아파트 중 한 아파트라도 조건을 만족하지 않는다면 조망권을 획득하지 못하기 때문에 네 채의 아파트 중 가장 높은 아파트에 대해서만 적용하면 된다.

코드

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	int test_case;
	int T = 10;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		int n;
        cin >> n;
        vector<int>v(n);
        
        for(int i=0;i<n;i++)
        {
        	cin >> v[i];
        }
        
        int cnt = 0;
        for(int i=2;i<n-2;i++)
        {
            int l = max(v[i-1],v[i-2]);
            int r = max(v[i+1],v[i+2]);
            if(v[i] <= l || v[i] <= r)
                continue;
            
            cnt += (v[i] - max(l,r));
        }
        
        cout << "#" << test_case << " " << cnt << "\n";
    }
	return 0;
}

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh