1206. [S/W 문제해결 기본] 1일차 - View D3

문제

SW Expert Academy

위의 그림같이 건물 좌우 2칸씩 아무것도 없으면 view가 보인다.

위의 그림에서는 초록색으로 칠해진 곳이 view가 보이는 곳이다. 따라서 총 6개가 view가 보인다.

A는 오른쪽으로 1칸때문에 안보이고 B도 마찬가지이다. C는 왼쪽으로 1칸때문에 안보인다.

맨 오른쪽, 왼쪽 2칸 씩은 건물의 높이가 0이다.

 

처음에는 스택과 큐로 접근 하였는데 계속 안풀려서 1시간 소비한 문제이다. 

답지를 보면 정말 간단한것 을 알 수 있다.

일단 모든 건물의 높이를 다 배열에 담고

현재 인덱스로 부터 left(-2, -1), right(+1, +2) 인 곳을 찾아 둘 중에 더 큰 건물의 높이에서 현재 건물의 높이를 뺴면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
using namespace std;
int arr[1001];
int main()
{
    for (int i = 1; i <= 10; i++)
    {
        int n; //건물의 개수
        cin >> n;
        int sum = 0; //view를 세는 변수
        int l = 0, r = 0;
        for (int j = 0; j < n; j++)
            cin >> arr[j];

        for (int j = 2; j < n - 2; j++)
        {
            l = max(arr[j - 1], arr[j - 2]);  //현재 건물 기준으로 왼쪽의 건물 중 더 높은 건물
            r = max(arr[j + 1], arr[j + 2]); //현재 건물 기준으로 오른쪽의 건물 중 더 높은 건물
            if (arr[j] > l && arr[j] > r) //만약 현재 건물이 양쪽 건물 보다 클 경우
            {
                int m = max(l, r); //왼쪽, 오른쪽 건물 중 큰 건물의 높이를 현재 건물의 높이에서 뺌
                sum += (arr[j] - m);
            }
        }
        cout << '#' << i << ' ' << sum << '\n';
    }

    return 0;
}