골랜디 #3 1027번

Published at: 2025-03-22

Last modified at: 2025-03-22

오늘 푼 문제

안녕하세요 한라나입니다.
저는 내일(오늘?) 도로주행 시험을 보러가기로 했어요.
저번에 두 시간 연습해보고 느낀 점은…
할만은 한데, 1n년동안 이걸 하면서 사고 한번 안 나는건 좀 힘들것 같다는 거였습니다.
사실 저는 비행기 조종이 더 쉽고 안전하다고 생각하는 사람이거든요. 물론 실제 비행기를 운전해본 적은 없습니다.

각설하고, 오늘 문제 제목은 아래와 같습니다.

브루트포스라니… 어제 풀었던 골드 3이랑 체감 난이도 차이가 너무 많이 나는걸요?
이 문제가 골드 4는 맞는걸까요??
시간 제한도 2초라니! 그냥 다 해보면 됩니다.

다 해본다는건 정확히는, 1번부터 n번 빌딩까지 돌면서, 본인 오른쪽에 있는 건물 옥상에 레이저 한번씩 쏴보고 중간에 길막하는 빌딩이 있는지 확인해보면 됩니다.
없다면, 본인 빌딩과 레이저 쏜 빌딩 둘 다 볼 수 있는 빌딩 숫자 +1을 하면 되니까, 오른쪽에 있는 건물만 봐도 되게 할 수 있습니다.

i번째 건물이 본인 건물이고 j번째 건물이 레이저 맞는 건물일때, 사이에 건물이 있는지 확인하는건 아래와 같이 하면 됩니다.
i보다 크고 j보다 작은 k에 대해 k번째 건물이 길을 막고 있는지 보는 코드니까, i+1부터 j-1까지 k에 대해 이걸 다 해보면 됩니다.

if(height[k]*1.0>=((height[i]*(j-k)+(height[j]*(k-i)))*1.0)/((j-i)*1.0)) check = false;

소수로 바꿔서 한것은 문제 조건에 겹처도 안 된다고 하길래, 좀 더 정확하게 하려고 했습니다.
그리고 건물 높이가 10억 까지니까, 곱하다가 터지지 않게 하려면 long long int를 써주는 것이 이롭습니다.

나머지는 1번 건물부터 n번 건물까지 보이는 건물 수를 비교해서 가장 큰 수를 출력하면 되겠네요.

원래 골드는 쉬운건데,,어제 저만 쓸데없이 헤멘걸까요,,,

감사합니다.

---

전체 코드

#include <stdio.h>

//using namespace std;

long long int max(int a, int b) {
    if(a>b) return a;
    else return b;
}

int main() {
    long long int n;
    scanf("%lld", &n);
    long long int height[60];
    long long int seeable[60] = {0, };
    long long int i;
    for(i=0;i<n;i++) {
        scanf("%lld", &height[i]);
    }
    for(i=0;i<n-2;i++) {
        long long int j;
        seeable[i]++;
        seeable[i+1]++;
        for(j=i+2;j<n;j++) {
            long long int k;
            bool check = true;
            for(k=i+1;k<j;k++) {
                if(height[k]*1.0>=((height[i]*(j-k)+(height[j]*(k-i)))*1.0)/((j-i)*1.0)) check = false;
            }
            if(check) {
                seeable[i]++;
                seeable[j]++;
            }
        }
    }
    if(n!=1) {
        seeable[n-2]++;
        seeable[n-1]++;
    }
    long long int ans = 0;
    for(i=0;i<n;i++) {
        ans = max(ans, seeable[i]);
    }
    printf("%d", ans);
    return 0;
}