백준 30409 나비와 전봇대 (Easy)

문제 

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

30409번: 나비와 전봇대 (Easy)

 

풀이

우선 p에서 왼쪽인 것만 생각해보자. 오른쪽인 것은 배열을 반대로돌리고 똑같이 생각해주면된다.

p와 어떤 전봇대를 이어줄지 선택해야할까? p에서 선택할 수 있는 전봇대는 하나이상이긴 할텐데 기하학적으로 깊게 들어갈 필요 없다.

Ha >= Hb >= p (a < b < index of p)일때 Ha를 선택가능한지(Hb와 중간에 교차하지 않는지) 여부와  p와 Hb를 잇는것, Ha를 잇는것중 무엇이 이득일지 생각할 필요가 없다. 이런 상황에선 무조건 Hb와 p를 이어주면된다.

왜냐하면...

 

(A-B는 전봇대 A와 B를 이어준 전선의 길이이다.)

(Ha와 p를 이어줄수 있고 Ha와 Hb를 이어줄 수 있고 Hb와 p를 이어줄 수 있다고 가정하자.)

1. Ha-p <= Ha-Hb + Hb-p

 직관적으로 그림을 그리면 알 수 있다. 전선의 길이는 Hb를 선택하면 길어진다.

2. 만약 Ha-p = Ha-Hb + Hb-p (세 전봇대를 한직선으로 이어줄 수 있음)라면 (Ha-Hb)^2 + (Hb-p)^2 < (Ha-Hb + Hb-p)^2이므로 Hb를 선택하는 것이 비용이 싸진다.

따라서 p의 왼쪽에 있는 p보다 높이가 크거나 같은 전봇대 중 p와 가장 가까운 전봇대와 이어주는 것이 최적이다.

 

dp: 각 전봇대에서 전선길이가 제일길고 그중 비용이 최소일때 전선길이 제곱의 합이라고하면

점화식은 다음과 같다: i에서 j(i>j)를 이어주는 것이 최적이라면 dp[i] = (Hi - Hj)^2 + (i-j)^2 + dp[j]

이제 i에서 j를 찾자. 만약 i와 j사이에 Hi보다 짧은 전봇대들이 있다면 이것을 다 무시해줘야한다.

이럴때 스택을 사용할 수 있다.

stack = []
dp = [0] * (원소개수)
for index,value in H:
	if (스택이 비지 않았다면):
    	// value보다 작은 원소들을 다 지워줌
    	while (스택이 비지않았고 스택의 마지막원소의 높이가 현재 스택보다 작다면):
        	stack.popback()
    if (스택이 비지 않았다면):
    	// dp채워주기
    	i,v = stack의 마지막
        dp[idx] = dp[i] + ((index,value)와 (i,v)사이의 거리 제곱)
    // 스택이 비었다면 왼쪽에 자신보다 크거나 작은게 없는 것이므로 0을 그대로 가져가면 된다.
    stack.append((index,value))

 

 

이렇게해서 왼쪽에서부터의 최적을 구할 수 있다.

오른쪽도 똑같이 구해준다. 나같은경우 배열을 반전시키고 똑같은 과정을 한 뒤에 얻은 dp를 다시 반전시켰다.

쿼리는 두 dp의 값을 더해주고 출력하면 된다.