[BOJ] 2300번: 기지국

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


D[i]를 0번째부터 i번째 건물까지 연결하는 설치비용의 최솟값이라고 둡니다. i번째 건물을 포함하는 기지국이 j번째 건물까지 포함한다고 가정할 경우 설치 비용은 max(j~i번째 건물 높이 중 최대 높이*2, i번째 건물과 j번째 건물 사이의 가로축 거리) + D[j-1]로 계산이 가능합니다. 그러면 j = 0~i까지 대입을 했을 때 D[i]를 갱신할 수 있게 됩니다. 이를 가지고 D[i]를 i번만에 구할 수 있고, 최종적으로 D[0]부터 쌓아올라가면 O(N^2)으로 답을 구할 수 있게 됩니다.


https://github.com/encrypted-def/BOJ/blob/master/2300.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 2261번: 가장 가까운 두 점  (2) 2018.01.07
[BOJ] 2515번: 전시장  (0) 2018.01.07
[BOJ] 2306번: 유전자  (0) 2018.01.07
[BOJ] 2250번: 트리의 높이와 너비  (2) 2018.01.07
[BOJ] 1239번: 차트  (0) 2018.01.07
[BOJ] 1017번: 소수 쌍  (0) 2018.01.07
  Comments