[백준, C++] 1027 - 고층 건물

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

1027번: 고층 건물

 

문제 분석

뭐랄까 ... 중학생 때 일차함수를 공부하면서 기울기 라는 개념을 배운 적이 다들 있을 것이다(중학교 때는 문이과 분리가 안 되니까 ... 아마 다 알 것이라고 생각함). 이 문제는 그 '기울기' 를 응용해서 푸는 문제인데, N이 최대 50이기 때문에 러프하게 3중 for문을 걸어도 시간 제한에 걸리지 않아 3중 for문으로 해결할 수 있다고 생각했다.

 

코드

#include <iostream>

using namespace std;

int n;
int buildings[51];
int counts[51];
int result;

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> buildings[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int building1 = buildings[i];
            int building2 = buildings[j];
            double rate = (double)(building2 - building1) / (double)(j - i);

            bool isBlind = false;
            for (int k = i + 1; k < j; k++) {
                double height = (double)building1 + rate * (double)(k - i);
                
                if (height <= buildings[k]) {
                    isBlind = true;
                    break;
                }
            }

            if (!isBlind) {
                counts[i]++;
                counts[j]++;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        result = max(result, counts[i]);
    }

    cout << result << "\n";
    return 0;
}

 

코드 설명

[1, N] 사이의 i, [i + 1, N] 사이의 j를 설정한다. 이 i와 j가 우리가 살펴볼 빌딩의 인덱스가 된다. buildings[i]와 buildings[j]로 얻은 빌딩 높이의 차는 y증분에 해당하고, j - i는 x증분에 해당한다. 기울기는 (buildings[j] - buildings[i]) / (j - i)로 표현할 수 있다.

 

그리고 [i + 1, j - 1] 사이의 빌딩의 높이를 볼 것이다. 우리는 앞서 구한 기울기를 활용해, i번 빌딩과 j번 빌딩 사이에 가상의 선을 그어볼 수 있을 것이고, k번 인덱스에서 가상의 선의 y좌표를 구할 수 있다. 이 y좌표를 height로 두는데, 만일 bulidings[k]가 height보다 크거나 같다면, i번 빌딩에서 j번 빌딩을 바라볼 때 k번 빌딩에 의해 j번 빌딩이 가려진다는 것을 의미하게 된다. 그래서 이런 상황이 되면 isBlind에 false를 할당해 안 보인다는 것을 체크해줄 수 있다.

 

[i + 1, j - 1] 구간에서 j번 빌딩을 가리는 k번 빌딩이 존재하지 않는다면, i번 빌딩과 j번 빌딩은 서로 볼 수 있는 위치에 있다. 따라서 counts[i]와 counts[j]를 1씩 증가시켜 준다. 그리고 counts[]를 순회하면서 최댓값을 찾아 반환하면 된다.

 

처음에는 골드4 문제여서 복잡한가 ? 어려운가 ? 를 생각했는데, 단순 기하였다. 그래서 큰 어려움 없이 풀 수 있었다.