https://www.acmicpc.net/problem/22975
| 시간 제한 | 메모리 제한 |
| 2초 | 1024MB |
문제
현욱이가 살고 있는 도시에는 N개의 빌딩이 있다. 빌딩은 전부 일렬로 세워져 있으며, 첫 번째 빌딩부터 차례대로 1번부터 N번까지 번호가 붙어 있다. 각 빌딩 사이의 간격은 모두 1로 동일하다. 여기서 i번째 빌딩의 높이를 Hi라고 할 때, 일렬로 서 있는 빌딩을 정면에서 바라볼 경우 i번째 빌딩은 (i, 0)과 (i, Hi)를 잇는 두께가 0인 선분으로 생각할 수 있다.
이때 임의의 i번째 빌딩과 j번째 빌딩에 대해서, i번째 빌딩의 옥상을 나타내는 점 (i, Hi)와 j번째 빌딩의 옥상을 나타내는 점 (j, Hj)를 잇는 선분이 다른 모든 빌딩과 만나지 않거나 빌딩의 끝점에서만 만날 경우 두 빌딩은 옥상에서 서로의 옥상을 볼 수 있다.
예를 들어 도시에 빌딩이 6개가 있고 첫 번째 빌딩부터 순서대로 높이가 2, 3, 7, 6, 1, 4 였다고 하자. 이 경우 각 빌딩을 직선으로 나타냈을 때 다음과 같이 그림을 그릴 수 있다.
예시에서 첫 번째 빌딩의 옥상에서 네 번째 빌딩의 옥상을 보려고 할 경우, 위 그림의 왼쪽과 같이 세 번째 빌딩에 가로막혀서 서로 옥상을 볼 수가 없다. 반면 세 번째 빌딩의 옥상에서 여섯 번째 빌딩의 옥상을 보려고 할 경우, 두 옥상을 이은 직선이 네 번째 빌딩의 옥상과 만나지만 끝점에서만 만나기 때문에 서로의 옥상을 볼 수 있다.
현욱이 살고 있는 도시의 시장은 어느날 새로운 도시 계획을 발표했다. 이 계획에 따르면, 도시에 있는 모든 빌딩은 옥상에서 다른 모든 빌딩의 옥상을 볼 수 있어야 한다.
안타깝게도 이 도시 계획을 만족시키기 위해서는 일부 빌딩을 파괴해야만 할 수도 있다. 시장은 파괴되는 빌딩의 개수를 최소화하고 싶다. 새로운 도시 계획을 위해 최소 몇 개의 빌딩을 파괴해야하는지 계산해보자.
입력
첫 줄에는 도시에 있는 빌딩의 개수 N(1 ≤ N ≤ 2,000)이 주어진다.
둘째 줄에는 도시에 있는 N개의 빌딩의 높이 Hi가 맨 왼쪽 빌딩부터 순서대로 공백으로 구분되어 주어진다(1 ≤ Hi ≤ 109).
출력
첫째 줄에 조건을 만족하기 위해 파괴해야하는 빌딩의 최소 개수를 출력한다.
풀이
빌딩을 막 그려서 아무렇게나 제거해보면 나타나는 패턴이 있습니다. 남아있는 빌딩들의 옥상만 점으로 표현한다면 대충 감소했다가 증가하는 포물선 형태여야 합니다. 그러니까 이웃한 두 빌딩의 옥상을 이은 선분의 기울기를 순차적으로 봤을 때 기울기가 최소 유지되거나 증가해야 합니다. 모든 서로 다른 빌딩 쌍에 대해 옥상을 잇는 선분의 기울기를 생각해봅시다.
모든 빌딩 쌍의 기울기를 정렬하면 기울기가 가장 작은 선분부터 꺼낼 수 있습니다. i번째 빌딩과 j번째 빌딩(i ≤ j)을 잇는 선분의 기울기가 a라고 했을 때, j번째 빌딩을 기준으로 했을 때 i번째 빌딩을 선택할 것인지 말 것인지를 따져볼 수 있습니다. 점점 기울기는 증가할 것이므로 선택하는 경우로만 생각할 수 있습니다. i-j 빌딩 쌍을 선택한다면 i번째 빌딩까지의 값에 j번째 빌딩을 하나 추가함으로써 j번째 빌딩까지의 선택되는 빌딩 개수를 늘려갈 수 있습니다.
i와 j 사이에 있는 빌딩들은 무시될 것 같지만 아닙니다. i와 j 사이의 빌딩들은 기울기가 더 작거나 큽니다. 기울기가 더 작았던 빌딩들은 이전에 확인을 해서 값 추가가 이미 이루어졌을 겁니다. 그 빌딩이 k라고 한다면 이후에 k-j 빌딩쌍의 기울기는 더 큽니다. 따라서 이후에 확인하며 값 추가를 할 수 있습니다. 기울기가 더 큰 빌딩 역시 이후에 확인하며 값 추가를 해나갈 수 있습니다.
점화식을 정리해봅시다. 기울기가 a인 i번째 빌딩과 j번째 빌딩 옥상을 이은 선분에 대해 j번째 빌딩까지를 선택하는 최적해는 다음과 같습니다.
dp[j] = max(dp[j], dp[i] + 1)
되게 간단하네요. 하지만 기울기를 기준으로 정렬하고 작은 값부터 꺼내 확인한다는 아이디어가 굉장히 어려웠습니다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
n = int(input())
h = list(map(int, input().split()))
inc = []
for i in range(n - 1):
for j in range(i + 1, n):
inc.append(((h[j] - h[i]) / (j - i), i, j))
inc.sort(key = lambda x: (x[0], x[2]))
dp = [1] * n
for i, a, b in inc:
dp[b] = max(dp[b], dp[a] + 1)
print(n - max(dp))
solution()
