[백준 알고리즘 C/C++] 1027번 문제 풀이: 고층 건물

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 백준 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] : 골드 4

백준 알고리즘 1027번 고층 건물

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

1027번: 고층 건물

 

 

---

● 풀이 방법

위 문제를 해결 하기 위해서는 선분 공식을 먼저 알아야 한다.

선분 공식 : y = ax + b

두 건물의 옥상을 x1,y1 / x2,y2로 하였을 때 두 점에서 잇는 선분을 긋는다.

해당 선분에 다른 건물이 간섭 될 경우, 두 건물은 서로 볼 수 없는 건물이 된다.

간섭이 되는 경우는 아래와 같다.

내가 기준으로 잡은 건물의 옥상(A)과 보고싶은 건물의 옥상(B)을 잇는 선분 공식을 먼저 구하고,

그 선분 공식에서 A와 B 사이에 있는 건물의 옥상 좌표 값을 대입하였을 때,

Y >= ax+b 가 true라면은 사이에 있는 건물이 A에서 B를 못보게 막고 있다 라고 볼 수 있다.

모든 건물들을 전체 탐색을 통해 볼 수 있는 건물의 수를 배열에 저장해서 가장 많이 볼 수 있는 건물의 수를 출력하면 된다.

---

● 소스 코드

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

using namespace std;

int main()
{
    int building_cnt;
    int result = 0;
    cin >> building_cnt;
    int budilding_list[building_cnt][2] = {0,}; // 빌딩번호[x값] , 빌딩의 높이 , 보이는 건물

    for(int i = 0; i < building_cnt; i++){
        cin >> budilding_list[i][0];
    }

    for(int i = 0; i < building_cnt; i++){
        int x1 = i;
        int y1 = budilding_list[i][0];
        for(int j = i+1; j<building_cnt; j++){
            int x2 = j;
            int y2 = budilding_list[j][0];
            //선분공식 -> y = ax + b
            double a1 = (y1-y2); // [x1 4 | y1 6][x2 11 | y2 7] -1 / -7
            double a2 = (x1-x2); // [x1 4 | y1 6][x2 11 | y2 7] -1 / -7
            double a = a1/a2; //(y1-y2)/(x1-x2); // [x1 4 | y1 6][x2 11 | y2 7] -1 / -7
            double b = y1 - a*x1;

            //바로 옆에 있는 건물이라면..
            if(j-i==1){
                budilding_list[i][1] += 1;
                budilding_list[j][1] += 1;
            }else {
                for(int k = i+1; k < j; k++){
                    //  y >= ax + b 라면.. 즉 사이에 가려지는 건물이 있다면.
                    if(budilding_list[k][0] >= a*k+b){
                        break;
                    }else{
                        if(k==j-1){
                            budilding_list[i][1] += 1;
                            budilding_list[j][1] += 1;
                        }
                    }
                }  
            }
        }
    }
    for(int i = 0; i < building_cnt; i++){
        if(result < budilding_list[i][1])
            result = budilding_list[i][1];
    }
    cout << result << endl;
    
    return  0;

}

 

 

 

---

● 결과

** 코드 길이가 상이 할 수 있습니다! 그러나 내용물은 같습니다.

    이유)  주석 및 더미 소스 유무