[개쉬운 풀이] 백준 1027 고층 건물

https://www.acmicpc.net/problem/1027

문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

생각

1. 맨 왼쪽부터 오른쪽 건물이 보이는 경우의 수를 생각한다.
2. 보이는 건물에 각각 +1을 해준다.
3. 그러면 왼쪽의 건물은 고려할 필요 없이 오른쪽 건물들만 고려하면 된다. (브루트포스)
4. 또한 문제에서 접선의 얘기가 나왔으므로 기울기가 앞 건물보다 높아야한다.
5. 기울기를 구해야 하므로 타입을 int가 아닌 double로 해주어야한다. (중요)

** 현재 건물에서 다음 건물(i)이 보이려면 다음과 같은 조건을 만족해야한다.

1. 앞에 계산한 기울기의 각도(i-1)보다 다음 건물의 기울기(i)가 더 커야한다.

풀이

1. N개의 건물이 아닌 N-1개의 건물에 대해 볼 수 있는 오른쪽 건물 수를 계산한다. : sol()
2. 해당 건물을 기준으로 for문을 통해 오른쪽 건물과의 기울기를 비교하여 기울기의 각도가 점점 높아지는 건물들만 계산하면된다. : process()
3. for문안에서 현재 건물과 타겟 건물의 기울기를 구한다. 이때 double타입을 사용해야한다. : get_incline()

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
typedef long double ld;
using namespace std;

int N;
vector<ll> buildings;
vector<int> check;

void input(){
    cin >> N;
    check = vector<int>(N,0);
    for(int i = 0; i < N; i++){
        int tmp;
        cin >> tmp;
        buildings.push_back(tmp);
    }
}

//현재 건물에서 오른쪽 건물만 고려하므로 뺄셈의 순서를 고려해 주었다.
ld get_incline(int target_idx, int current_idx){
    ld x = current_idx - target_idx;
    ld y = buildings[current_idx] - buildings[target_idx];

    return y / x;
}

void process(int target_idx){
    check[target_idx] += 1;
    check[target_idx+1] += 1;
    ld incline = get_incline(target_idx, target_idx+1);
    for(int i = target_idx+2; i < N; i++){
        ld tmp = get_incline(target_idx, i);
        if(tmp > incline){
            incline = tmp;
            check[target_idx] += 1;
            check[i] += 1;
        }
    }
}

void sol(){
    //맨 오른쪽 건물은 비교할 대상이 없으므로 N-1까지만 반복문 실행
    for(int i = 0; i < N-1; i++){
        process(i);
    }

    int answer = 0;
    for(int i = 0; i < N; i++){
        answer = max(answer, check[i]);
    }

    cout << answer;
}

int main(){
    input();
    sol();
    return 0;
}