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

문제

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

SW Expert Academy

 

풀이

건물은 왼쪽에서 3번째 칸부터 오른쪽에서 3번째 칸까지 존재한다.

조망권이 확보된 세대는 왼쪽 2칸, 오른쪽 2칸에 다른 세대가 없어야 한다. 즉, 왼쪽 2칸, 오른쪽 2칸에 있는 건물보다 높으면 조망권이 확보된 세대가 존재한다.

 

이를 이용하여 다음과 같이 문제를 풀 수 있다.

1. 왼쪽에서 3번째 건물부터 오른쪽에서 3번째 건물까지 탐색한다.
    => i의 범위는 2 ~ n-3이다.
2. 현재 탐색하는 건물이 왼쪽의 두 건물과 오른쪽의 두 건물보다 높으면 조망권이 확보된 세대가 존재한다.
    => 현재 탐색하는 건물 i와 i-2, i-1, i+1, i+2번째 건물을 비교한다.
3. 현재 탐색하는 건물에서 조망권이 확보된 세대의 개수를 계산한다.
    => i번째 건물의 높이 - 양 옆 4개의 건물 중 가장 높은 건물의 높이

 

코드

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int T = 10;

    for (int test_case = 1; test_case <= T; ++test_case) {
        int n, ans = 0;

        // 입력
        cin >> n;

        vector<int> building(n, 0);
        for (int &i: building)
            cin >> i;

        // 연산
        for (int i = 2; i < n - 2; i++) {
            int max_building = max(max(building[i + 1], building[i + 2]), max(building[i - 1], building[i - 2]));
            if (building[i] > max_building)
                ans += building[i] - max_building;
        }

        // 출력
        cout << '#' << test_case << ' ' << ans << '\n';
    }

    return 0;
}