[ 백준 1027 ] 고층 건물 (C++) - BruteForce

---

🔗 문제 링크

1027번: 고층 건물

---

💡 문제 풀이 및 해석

1. 입력이 50개라는 제한이 있었다.
2. 2초라는 50개에 비한 비교적 널널한 시간제한이 있었다.
3. 위의 두가지 조건을 고려하여 brute force로 진행.

 

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int N;
int cnt[50];
vector<int> building;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int Height; cin >> Height;
        building.push_back(Height);
    }
}

void cul_incline() {
    for (int M = 0; M < N; M++) { // 살펴볼 건물
        float Left = 100000000000.0;
        float Right = -10000000000.0;
        for (float L = M - 1; L >= 0; L--) { // 이 건물이 왼쪽으로 볼 수 있는 빌딩
            float L_in = (building[M] - building[L]) / (M - L);
            if (L_in < Left) { // 기울기가 더 낮아야 볼 수 있음
                Left = L_in;
                cnt[M]++;
            }
        }
        for (float R = M + 1; R < N; R++) { // 이 건물이 왼쪽으로 볼 수 있는 빌딩
            float R_in = (building[R] - building[M]) / (R - M);
            if (R_in > Right) { // 기울기가 더 높아야 볼 수 있음
                Right = R_in;
                cnt[M]++;
            }
        }
    }
}

int main() {

    input();
    cul_incline();
    int answer = 0;
    for (int i = 0; i < N; i++) {
        answer = max(answer, cnt[i]); // 최대값 출력
    }
    cout << answer;
    return 0;
}

 

---

🤔 문제 후기

풀이를 진행하면서 아래 코드에서 L과 R을 int로 진행하였는데, 어째선지 float X = int/int 이면 X가 당연히 float로 되는줄 알았는데, int형으로 되서 예제를 통과하지 못했었다. L과 R을 float로 바꿔서 계산하니 결국 통과를 하였지만, 이보다는 float(R-M) 과 같은 형태가 더 나을 것 같다는 생각을 하였다.

for (float L = M - 1; L >= 0; L--) { // 이 건물이 왼쪽으로 볼 수 있는 빌딩
            float L_in = (building[M] - building[L]) / (M - L);
            if (L_in < Left) { // 기울기가 더 낮아야 볼 수 있음
                Left = L_in;
                cnt[M]++;
            }
        }
        for (float R = M + 1; R < N; R++) { // 이 건물이 왼쪽으로 볼 수 있는 빌딩
            float R_in = (building[R] - building[M]) / (R - M);
            if (R_in > Right) { // 기울기가 더 높아야 볼 수 있음
                Right = R_in;
                cnt[M]++;
            }
        }​