[BOJ] 1027 고층건물

BOJ 1027 고층 건물 https://www.acmicpc.net/problem/1027

 

이게 처음에 무슨 소리인가.. 문제가 헷갈렸었는데 

 

입력되는 값들을 차트로 표현하니까 이해하기가 쉬워 졌다.

 

 

위의 차트에서 볼 수 있듯이 5번 건물에서 다른 건물을 보는 LOS(Line of Sight)를 그었을 때 

 

좌측의 경우에는 4, 3, 2번 건물까지는 볼 수 있지만, 1번 건물의 경우는 2번 건물에 막혀서 볼 수 없고

 

우측의 경우에는 6, 7, 8번 건물 까지 보고, 9, 10 ,11번 건물을 8번 건물에 막혀서 볼수 없다가, 

 

또 12번 건물은 볼 수 있고, 13, 14, 15번 건물은 12번 건물에 박혀서 볼 수 없는 상황에 놓이게 된다. 

 

특정 건물에 막혀서 볼 수 없다는 말의 의미를 고민해 보면 이 문제의 풀이에 대한 실마리를 알 수 있다.

 

어떤 건물에서 볼 수 있는 모든 건물을 알기 위해서는 해당 건물부터 다른 건물까지의 기울기를 보면 된다.

 

가까운 건물부터 고려하면서 계속해서 기울기의 최댓값과 최솟값을 갱신해주면되는데, 

 

이 때 볼 수 있는 건물은 좌측의 경우, 기울기의 최솟값을 갱신하면서 현재 기울기보다 작은 기울기를 가지는 건물을 볼 수 있고,

 

우측의 경우, 기울기의 최댓값을 갱신하면서 현재 기울기보다 큰 기울기를 가지는 건물을 볼 수 있다.

 

5번 건물을 예로 들면, 좌측은 초기에 기울기의 최솟값을 -INF/-1이라고 하고, 4, 3, 2번 건물을 보면 기울기가 -4/-1, -3/-2, -1/-3으로 점점 작아지는데, 1번 건물의 경우 기울기가 -5/-4가 되어서 기울기가 최솟값보다 커져서 볼 수 없게 된다.

 

우측의 경우, 초기에 기울기의 최댓값을 -INF/1이라고 하고, 6, 7, 8번 건물을 보면 기울기가 -3/1, -4/2, 0/3으로 점점 커지는 모습을 볼 수 있고, 9, 10, 11번 건물은 기울기가 -2/4, -4/5, -1/6이 되어서 현재까지의 기울기 최댓값인 0보다 작아서 볼 수가 없다. 그 다음에 보이는 12번 건물은 기울기가 1/7이 되어 최댓값 0보다 커서 볼수사 있고, 13, 14, 15번 건물은 기울기가 -3/8, -4/9, -1/10이 되어서 기울기의 최댓값보다 작으므로 볼수가 없게 된다.

 

이와 같은 방법으로 모든 건물에 대해 볼 수 있는 건물을 세보면 5번건물에서 7개, 12번 건물에서 7개를 볼 수 있어서 최대 7개의 건물을 볼 수 있게 된다.

 

위와 같은 풀이를 하기 위해서 아래와 같은 기울기를 정의하는 구조체를 만들었다.

struct tilt {
    lld x, y;
    tilt(){}
    tilt(lld x, lld y):x(x), y(y){}
    bool operator < (tilt v) const {
        return  v.x * y < v.y * x;
    }
    tilt& operator = (const tilt& c) {
        x = c.x;
        y = c.y;
        return *this;
    }
};

전반적으로 간단한 구조체이긴 한데, operator =을 정의할 때  처음에 return type을 void로 정의하는 바람에 한참을 헤멘것 같다.

 

이 구조체를 이용해서 작성한 코드는 아래와 같다.

#include <stdio.h>
#define lld long long
#define INF 2e9
lld n, h[52];
 
struct tilt {
    lld x, y;
    tilt(){}
    tilt(lld x, lld y):x(x), y(y){}
    bool operator < (tilt v) const {
        return  v.x * y < v.y * x;
    }
    tilt& operator = (const tilt& c) {
        x = c.x;
        y = c.y;
        return *this;
    }
};
 
int main(){
    scanf("%lld", &n);
    for (lld i = 1; i <= n; ++i) scanf("%lld", &h[i]);
    lld res = 0;
    tilt mx, mi, tmp;    
    for (lld i = 1; i <= n; ++i) {
        lld cnt = 0;
        mi = tilt(-1, -INF);
        for (lld j = i - 1; 1 <= j; --j) {
            tmp = tilt(j - i, h[j] - h[i]);
            if (tmp < mi) {
                mi = tmp;
                cnt++;
            }
        }
 
        mx = tilt(1, -INF);
        for (lld j = i + 1; j <= n; ++j) {
            tmp = tilt(j - i, h[j] - h[i]);
            if (mx < tmp) {
                mx = tmp;
                cnt++;
            }
        }
        res = res > cnt ? res : cnt;
    }
    printf("%lld\n", res);
    return 0;
}

요새 STL없이 코딩하기위해 operator 사용법에 좀더 익숙해 져야 할듯 하다.