[c++] BOJ 1027 :: 고층 건물

문제

고층 건물 문제 바로가기

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

 

풀이

• 기울기를 비교하여, 더 급격한 기울기가 나오면 보이지 않는 것으로 판단
• 가장 급격한 기울기를 계속 갱신
• 왼쪽, 오른쪽에 대해서 각각 보이는 건물 개수 계산
• 올려다볼 수도 내려다볼 수도 있음

 

코드

#include <iostream>
#include <math.h>

using namespace std;
int N;
long long height[50];

struct multiType {
    long long common;
    long long aMulti;
    long long bMulti;
    multiType(int c, int a, int b) {
        common = c;
        aMulti = a;
        bMulti = b;
    }
};

multiType* getCommonMulti(long long a, long long b) {
    long long aMulti = 2; long long bMulti = 2;
    long long newA = a; long long newB = b;
    while (newA != newB) {
        if (newA < newB) newA = a*aMulti++;
        else newB = b*bMulti++;
    }

    return new multiType(newA, aMulti-1, bMulti-1);
}

bool isUpSlope(pair<long long, long long> newIncline, pair<long long, long long> oldIncline) {
    auto multi = getCommonMulti(newIncline.second, oldIncline.second);

    newIncline.first *= multi->aMulti;
    newIncline.second *= multi->aMulti;
    oldIncline.first *= multi->bMulti;
    oldIncline.second *= multi->bMulti;

    if (newIncline.first > oldIncline.first) return true;
    else return false;
}

int getShownBuilding(int idx) {
    // 내려다볼 수도 있구나!
    int num = 0;
    pair<long long, long long> leftIncline = make_pair(-1e9, 1); // 분자 / 분모
    for (int i = idx-1; i >= 0; i--) {
        // 왼쪽
        pair<long long, long long> newIncline = make_pair(height[i] - height[idx], idx - i);

        if (!isUpSlope(newIncline, leftIncline)) continue;
        num++;
        leftIncline = newIncline;
    }

    pair<long long, long long> rightIncline = make_pair(-1e9, 1); // 분자 / 분모
    for (int i = idx + 1; i < N; i++) {
        // 오른쪽
        pair<long long, long long> newIncline = make_pair(height[i] - height[idx], i - idx);

        if (!isUpSlope(newIncline, rightIncline)) continue;
        num++;
        rightIncline = newIncline;
    }

    return num;
}

int main() {
    // N은 50보다 작음
    // 하나씩 조회하면서 좌우로 기울기 유지하면서 몇 개인지 세기 (기울기가 더 급격해지면 해당 기울기로 갱신
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> height[i];
    }


    int result = 0;
    for (int i = 0; i < N; i++) {
        int num = getShownBuilding(i);
        if (result < num) result = num;
    }
    cout << result;
}

 

개선

• isUpSlope를 doudle의 나눗셈 계산으로 바꾸면 편했겠따.

 

결과

아이디	메모리	시간	코드 길이
gmldms784	2020	0	2037