<백준> 고층 건물(Gold 4)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/고층 건물 at main · heesoo-park/ForCodeKata

제출 결과

---

 

뭔가뭔가 빠르게 지나갔던 어제 일정을 마치고 오늘 또 새로운 문제 도전~!!

이 문제는 보자마자 이전에 풀었었던 스카이라인 문제나 탑 문제가 생각났었다.

그래서 스택을 사용하는 거려나 했는데... 숫자 제한이 너무나 작더라

최대 건물의 개수가 50밖에 안 된다...

그래서 이건 오히려 브루트포스를 사용하는 거에 가깝겠다는 생각으로 수정했다.

 

이 문제에서 구해야하는 건 각 빌딩에서 고층 빌딩이 보이는 개수를 구하고 거기서 나오는 최대값이다.

중간에 걸리는 게 없어야 뒤에 있는 빌딩이 보일 것이었다.

그리고 양쪽으로 다 확인을 해야했다.

뭔가 기울기를 사용해야할 거 같다는 느낌은 왔지만 이걸 어떻게 수학적으로 정리해야할지가 감이 안 왔다.

그러다가 알게 되었다.

 

한 건물을 기준으로 좌측, 우측을 따로 기울기 계산하여 좌측의 경우에는 최소 기울기를 저장하고 현재 기울기가 더 작은지 체크, 우측의 경우에는 최대 기울기를 저장하고 현재 기울기가 더 큰지를 체크하면 된다는 것을...!

 

좌측에서는 기준이 되는 빌딩이 우측 끝을 맡고 있기 때문에 직선의 기울기에서 앞쪽을 맡고 있는 것이다.

그렇기 때문에 기울기가 점점 작아져지는 방향이 되어야지 최대한 많은 빌딩 건물을 볼 수 있다.

우측에서는 기준이 되는 빌딩이 좌측 끝을 맡고 있기 때문에 직선의 기울기에서 뒤쪽을 맡고 있는 것이다.

그렇기 때문에 기울기가 점점 커지는 방향이 되어야지 최대한 많은 빌딩 건물을 볼 수 있다.

최대, 최소 기울기를 저장해놓는 것은 중간에 그렇게 기울기가 튀는 애들이 있으면 뒤에 있는 건물들은 무조건 가려지기 때문이다.

 

이 흐름을 잡으니까 구현은 아주 쉽게 할 수 있었다.

물론 좀 이상한게 나왔다.

기울기를 구할 때 분명 타입 캐스팅을 해줬고 수식을 사용했는데 다른 값이 나왔다.

// buildings[i] = 7, buildings[j] = 1
// i = 2, j = 0 인 경우

val cur = buildings[i] - buildings[j] / (i - j).toDouble()
// 결과 : 6.5

val cur = (buildings[i] - buildings[j]).toDouble() / (i - j).toDouble()
// 결과 : 3.0

이거에 대해서는 혹시 이유를 아신다면 댓글을 좀...

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.BufferedWriter
import java.io.OutputStreamWriter

private lateinit var buildings: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val n = readln().toInt()

    buildings = readln().split(' ').map { it.toInt() }.toIntArray()

    bw.write("${solve(n)}\n")
    bw.flush()
    bw.close()
}

fun solve(n : Int): Int {
    var result = 0
    for (i in 0 until n) {
        var cnt = 0
        if (i != 0) {
            var prev = 0.0
            for (j in i - 1 downTo 0) {
                prev = if (j == i - 1) {
                    cnt++
                    (buildings[i] - buildings[j]).toDouble() / (i - j).toDouble()
                } else {
                    val cur = (buildings[i] - buildings[j]).toDouble() / (i - j).toDouble()
                    if (cur < prev) cnt++

                    minOf(prev, cur)
                }
            }
        }

        if (i != n - 1) {
            var prev = 0.0
            for (j in i + 1 until n) {
                prev = if (j == i + 1) {
                    cnt++
                    (buildings[j] - buildings[i]).toDouble() / (j - i).toDouble()
                } else {
                    val cur = (buildings[j] - buildings[i]).toDouble() / (j - i).toDouble()
                    if (cur > prev) cnt++

                    maxOf(prev, cur)
                }
            }
        }

        result = maxOf(result, cnt)
    }

    return result
}

 

참고)

https://nerogarret.tistory.com/57