[BOJ] 1027번 : 고층 건물

PS공부하기 싫어서 쉬워보이는 문제로 아무거나 골라 풀었다. 의외로 재미있어서 좋았다.

 

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

1027번: 고층 건물

 

아이디어는 역시 간단하다. 한 건물을 중심으로 다른 두 방향으로 쭉 뻗어나가면서 gradient를 계산해 주면 된다.

 

예를 들어 다음과 같은 입력에서 5번째 건물을 보자.

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

5번째 건물의 높이는 6이다. 

 

어느쪽 방향이든 첫 번째 건물을 무조건 볼 수 있다. 따라서 첫 번째 건물을 기준으로 gradient를 설정해 주면 된다. 6번째 건물의 높이는 3이므로 gradient는 -3으로 설정된다. 즉, 5번째 건물을 기준으로 오른쪽으로 d만큼 떨어진 건물의 경우에는 높이가

보다 크면 그 건물을 관측할 수 있다. (h[stdIdx]는 관측자가 있는 건물의 높이이다.)

 

7번째 건물의 높이는 2이므로 6-3d인 0보다 크고, 관측할 수 있다. 따라서 gradient를 갱신한다. gradient는 따라서 -2가 된다. 8번째 건물의 높이는 6이므로 6-2d인 0보다 크고, 관측할 수 있다. gradient는 0으로 갱신된다. 

 

이후 9번째, 10번째, 11번째 건물은 공식에 의한 6보다 높이가 작으므로 관측할 수 없고 12번째 건물이 오른쪽에서 관측할 수 있는 마지막 건물이다.

 

이 과정은 countForward(int stdIdx, double grad, int nowIdx) 함수를 통해 재귀적으로 구현하였다.

왼쪽으로도 같은 과정으로 계산해 주면 되는데, countBackward(int stdIdx, double grad, int nowIdx) 로 구현하였다.

 

시간복잡도는 

이다. N이 매우 작으므로 괜찮은 시간복잡도이다.

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAXN = 55;
 
int n ;
double h[55];
 
int countForward(int stdIdx, double grad, int nowIdx) {
    
    if(nowIdx > n) return 0;
    
    if(h[nowIdx] > h[stdIdx] + grad*(nowIdx-stdIdx)) {
        return countForward(stdIdx, (h[nowIdx]-h[stdIdx])/((double)(nowIdx-stdIdx)), nowIdx+1) +1;
    }
    else return countForward(stdIdx, grad, nowIdx+1);
    
}
 
int countBackward(int stdIdx, double grad, int nowIdx) {
    if(nowIdx < 1) return 0;
    
    if(h[nowIdx] > h[stdIdx] + grad*(stdIdx-nowIdx)) {
        return countBackward(stdIdx, (h[nowIdx]-h[stdIdx])/((double)(stdIdx-nowIdx)), nowIdx-1) +1;
    }
    else return countBackward(stdIdx, grad, nowIdx-1);
    
}
 
int main ( void ) {
    
    int maxVal = 0, sum;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lf", &h[i]);
    
    for(int i = 1; i <= n; i++) {
        sum = countForward(i, (h[i+1]-h[i]) -1, i+1) + countBackward(i, (h[i-1]-h[i])-1, i-1);
        maxVal = max(maxVal, sum);
    }
    printf("%d", maxVal);
}

 

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/1027/1027.cpp

Jordano-Jackson/PS