[GoLang] 백준 1027번, 고층 건물 풀어보기

개요

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

백준의 고층 건물 문제를 풀어봅시다

 

문제를 정리하면 다음과 같습니다.

 

단위가 1인 직성상에 건물이 50보다 작거나 같은 수로 주어지고 이는 차례대로 세워지는데

이 건물들의 높이는 1,000,000,000보다 작다.
이때 한 빌딩에서 올라갔을 때 가장 많은 빌딩이 보이는 수는 몇 개인가?

 

이때 빌딩이 보인다는 개념은 단순히 건물의 높이가 높다고 보이는 게 아니고 

한 빌딩에서 보는 시각을 기준하기에 이를 풀기 위해서는 단순한 높이차가 아닌 보이는  시각

즉 현재 빌딩과 바라볼 빌딩의 간의 기울기를 기준으로 문제를 다가가야 합니다.

 

기울기 공식은 다음과 같습니다

기울기 = y의 증가량/x의 증가량

 

기울기를 베이스로 문제를 풀면 다음과 같은 그림이 나옵니다.

 

아래 설명에서 사용되는 이미지들은 아래 블로그의 이미지를 가져왔습니다. (감사합니다)

https://nerogarret.tistory.com/57

[백준 알고리즘: python 3] #1027 - 고층 건물

빨간 직선이 현재 좌표이고, 빨간원이 보이는 기울기, 빨간 x는 보이지 않는 기울기 입니다.

 

현재 빌딩을 기준으로 바라볼 빌딩들이 우측에 해당할 경우 위 그림처럼 단순하게 이전 빌딩보다 더 큰 기울기를 지닌다면 보이게 됩니다

 

하지만 아래 그림처럼 좌측에 해당할 경우는 조금 다르게 됩니다.

기울기를 같은 공식으로 구했을 때 더 작은 기울기가 보이게 되는 걸 알 수 있습니다.

 

기울기를 구했을 때 오른쪽과 마찬가지로 기울기가 더 큰 게 아닌 더 작은 게 보이게 됩니다.

빌딩의 시작점이 반전이 되었으므로 기울기 또한 부호가 반대로 적용되게 됩니다.

 

이 점만 유의하시고 코드를 작성하면 한 번에 맞으실 겁니다.

 

코드

위 논리로 코드를 짜면 아래와 같습니다

 

저는 빌딩 수만큼 반복문을 돌며 현재 빌딩을 구하고 그 빌딩 값을 기준으로 좌측, 우측의

빌딩이 보이는 개수를 계산했습니다.

 

package main

import (
	"fmt"
	"math"
)

func main() {
	var count int
	result := 0
	fmt.Scanln(&count)
	building := make([]int, count)
	visible := make([]int, count)

	for i := 0; i < count; i++ {
		fmt.Scan(&building[i])
	}

	for i := 0; i < count; i++ {
		// 왼쪽 방향으로 보이는 빌딩, 기울기가 작아야 보임
		lastInclination := math.Inf(1)
		for left := i - 1; left >= 0; left-- {
			inclination := float64(building[i]-building[left]) / float64(i-left)
			if inclination < lastInclination {
				visible[i]++
				lastInclination = inclination
			}
		}

		// 오른쪽 방향으로 보이는 빌딩, 기울기가 커야 보임
		lastInclination = math.Inf(-1)
		for right := i + 1; right < count; right++ {
			inclination := float64(building[right]-building[i]) / float64(right-i)
			if inclination > lastInclination {
				visible[i]++
				lastInclination = inclination
			}
		}

		if result < visible[i] {
			result = visible[i]
		}
	}
	fmt.Println(result)
}