[백준]1027 고층건물 - 골드4

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• 브루트포스 탐색, 구현, 수학

---

1. 문제설명

 

세준시에 위치한 고층 빌딩이 한줄로 이어질 때 현재 빌딩을 기준으로 보이는 모든 빌딩을 찾는 문제입니다.

---

[제한사항]

• 시간 제한 2초
• 메모리 제한 128MB
• N은 50보다 작거나 같은 자연수
• 빌딩의 높이는 1보다 크고 1,000,000,000 보다 작거나 같은 자연수

---

2. 접근방식

 

단순히 현재 빌딩을 기준으로 이 빌딩보다 낮은 건물을 찾는게 아닌 시야각이 중요한 문제입니다.

 

현재 빌딩을 기준으로 다음번 빌딩을 j라고 지정할 때, 그 빌딩 사이에 있는 빌딩들의 시야각이 i와 j 빌딩의 시야각보다 낮아야지만 보인다고 판별이 되는 문제입니다.

 

https://velog.io/@vkdldjvkdnj/boj01027

[BOJ 1027] - 고층 건물 (기하학, 브루트포스, Python)

이분이 설명을 아주 잘해주셨습니다.

저도 문제를 풀다가 제대로 이해가 되지 않아서 설명을 참조했고 많은 도움을 받았습니다.

 

문제의 핵심은 다음과 같습니다.

기준이 되는 빌딩을 기준으로 중간에 위치한 모든 빌딩의 시야각을 계산했을 때 그 각이 볼록한 경우 볼 수 없는 빌딩이고

각이 아래로 오목한 경우 볼 수 있는 빌딩인 것입니다.

 

우리가 실제로 높은 빌딩에 올라가 다른 빌딩을 본다고 할 때의 시야각을 생각하면 편할것 같습니다.

 

이를 코드로 구현해 보았습니다.

---

3. 코드

import sys
input = sys.stdin.readline

N = int(input())  
building = list(map(int, input().split()))  
answer = 0  

# 모든 빌딩을 기준으로 삼아 탐색
for i in range(N):
    temp = N - 1  # 처음엔 i를 제외한 모든 빌딩이 보인다고 가정 (N-1개)

    # 오른쪽에 있는 빌딩들을 탐색
    for j in range(i + 1, N):  

        # i와 j 사이의 모든 빌딩이 시야를 가리는지 확인
        for k in range(i + 1, j):  

            if building[k] - building[i] >= (((building[j] - building[i]) / (j - i)) * (k - i)):
                temp -= 1  # j번 빌딩은 i번에서 안 보이므로 카운트에서 제외
                break  # 하나라도 가리면 그 j는 볼 수 없으니 중단

    # 왼쪽에 있는 빌딩들을 탐색
    for j in range(0, i):  
        for k in range(j + 1, i):  # k는 j와 i 사이에 있는 중간 빌딩
            # j와 i를 이은 직선보다 building[k]가 높거나 같으면 가려짐
            if building[k] - building[j] >= (((building[i] - building[j]) / (i - j)) * (k - j)):
                temp -= 1  # j번 빌딩은 i번에서 안 보이므로 카운트에서 제외
                break  # 가리면 더 볼 필요 없음
    answer = max(temp, answer)
print(answer)

---

[코드설명]

# 모든 빌딩을 기준으로 삼아 탐색
for i in range(N):
    temp = N - 1  # 처음엔 i를 제외한 모든 빌딩이 보인다고 가정 (N-1개)

    # 오른쪽에 있는 빌딩들을 탐색
    for j in range(i + 1, N):  

        # i와 j 사이의 모든 빌딩이 시야를 가리는지 확인
        for k in range(i + 1, j):  

            if building[k] - building[i] >= (((building[j] - building[i]) / (j - i)) * (k - i)):
                temp -= 1  # j번 빌딩은 i번에서 안 보이므로 카운트에서 제외
                break  # 하나라도 가리면 그 j는 볼 수 없으니 중단

 

코드의 동작 과정을 쉽게 설명해 보겠습니다.

 

현재 기준이 되는 빌딩 i에서 j번째 빌딩을 보려고 합니다.

 

두 빌딩 사이를 직선으로 그었을 때 그 직선 아래에 위치하는 빌딩들은 시야에 보이는 빌딩이겠죠

여기서 j 빌딩의 높이가 높다면 직선은 위로 올라갈 것입니다.

 

기준점 i에서 보고자 하는 빌딩 j까지의 기울기를 구하는 방식은 

(높이 / 거리) 로 구할 수 있습니다.

 

그럼 두 빌딩 사이의 높이는 j에서 i를 빼주면 해당 빌딩의 높이차가 나오겠죠

두 빌딩 사이의 거리는 j - i가 될 것입니다.

 

이 때 이 두 빌딩 사이에 있는 빌딩들이 가리는지 판별해 주어야 합니다.

그 가리는지 판별을 k를 이용해 구해준 것입니다.

 

두 빌딩 사이의 건물 수는 i와 j 사이의 빌딩을 탐색하여 구할 수 있습니다.

 

그때 k번째 빌딩이 시야선 보다 높거나 같다면 j번째 빌딩이 가리게 됩니다.

 

즉 기준이 되는 i번째 빌딩과 현재 k번째 빌딩의 높이차이가

시야각보다 높다면 j번째 빌딩이 보이지 않는 것입니다.

 

이렇게 중간에 가리는 빌딩이 있다면 기준빌딩 i에서 j가 보이지 않으므로 temp에서 1씩 빼주는 것입니다.

이걸 i를 기준으로 모든 오른쪽 빌딩을 탐색하면 최소한 보이는 빌딩의 갯수가 정해지고 동일하게 왼쪽도 탐색해 주는 것입니다.

---

    # 왼쪽에 있는 빌딩들을 탐색
    for j in range(0, i):  
        for k in range(j + 1, i):  # k는 j와 i 사이에 있는 중간 빌딩
            # j와 i를 이은 직선보다 building[k]가 높거나 같으면 가려짐
            if building[k] - building[j] >= (((building[i] - building[j]) / (i - j)) * (k - j)):
                temp -= 1  # j번 빌딩은 i번에서 안 보이므로 카운트에서 제외
                break  # 가리면 더 볼 필요 없음

 

왼쪽에 있는 빌딩은 이미 진행 되었다면 j보다 오른쪽에 있겠죠

 

이를 이용해 j를 왼쪽으로 설정하고 그 사이에 존재하는 빌딩들을 동일하게 k로 구해줍니다.

 

여기서도 시야각을 계산하는데 k에서 i 의 높이차가 더 크다면 빌딩이 가리게 되니 i에서 j번 빌딩이 보이지 않는다고 판단하고 temp를 1씩 빼주는 것입니다.

 

이 과정을 완료하면 temp에는 i번째 빌딩을 기준으로 왼쪽에서 보이는 빌딩의 수, 오른쪽에서 빌딩이 보이는 수가 나옵니다.

이를 answer에 업데이트 하며 기준 빌딩을 오른쪽으로 이동시키며 전체 탐색을 실시하는 것입니다.

---

4. 결과

---

[회고]

이번 문제를 풀면서 어 왜 틀리지 이런 경우가 많았습니다.

 

처음 문제를 보고 단순히 현재 빌딩보다 낮은 빌딩을 다 찾으면 되는거 아닌가? 라는 생각으로 접근해서 문제를 해결하려고 했는데

그렇게 풀어보니 테스트케이스 1번이 14가 나왔습니다.

 

생각해보니 중간 높이 7이 가장 높은 빌딩이니 해당 빌딩보다 낮은 빌딩의 갯수를 모두 세면 전체 빌딩수 -1 이 출력되는 것이었습니다.

 

여기서 생각이 잘못되었구나를 깨닫고 그럼 어떻게 구해야 하지 하고 생각을 많이 했습니다.

 

저는 문과 출신이라 수학에 자신이 없는데 문제의 설명에 선분이 나와있어서 이걸 어떻게 이용해야 하나 하고 고민을 많이 했습니다.

 

그러다 앞서 참고링크를 달아둔 블로그의 설명을 보고 아 시야각을 구하는 문제구나 라고 알게되었고

두 선분의 시야각을 구하는 방법을 구글링 하였습니다.

 

구글링을 통해 찾아 시야각을 구하는 방법을 알게 되었고 코드를 작성하며 코드에 적용해 보았는데

 

단순히 시야각은 구했는데 다음은 빌딩의 갯수를 찾는게 문제였습니다.

 

그래서 생각을 달리해 처음 빌딩을 기준으로 모든 빌딩이 보인다고 가정할 때 빌딩이 가리는 경우를 찾아 주엇습니다.

 

즉 두 빌딩의 선분을 기준으로 시야각이 위로 올라가는 경우를 찾아준 것입니다.

 

그렇게 해서 문제를 해결할 수 있었고 정답을 맞출 수 있었습니다.

 

전 이번 문제는 처음에 되게 쉽게 접근했다가 제대로 풀리지 않아서 고민을 많이 했던 문제입니다.

 

1일전 솔브가 해당 블로그의 코드를 보고 어떻게 돌아가지 하고 돌려본 코드 였습니다.

 

그러나 그렇게 해결하는 문제는 제 실력이 아니기 때문에 다른 방법을 찾고자 문제를 돌려보았고 1번 틀린 후 코드의 수정을 거쳐 모든 테케를 맞춰 블로그를 작성했습니다.

 

제 코드가 맞다고 생각하다가 정답 안돌렸구나 생각한건 비밀

 

아무튼 이렇게 문제를 해결할 수 있었고 수학적 사고를 하게되었습니다.