sgc109   6년 전

문제에서 주어진 장독대의 가치 V와 온도 T의 순서를 뒤집어서 이런식을 세웠습니다.


Dij : i에 꺼냈고 j에 넣는 김치싸대기의 맛

Dij = Vj + (j - i) * Ti

= Ti * j - Ti * i + Vj


T의 순서를 뒤집었으니 Ti <= Ti+1 이 되는데 최대값을 구하는것을 최소값을 구하는것으로 바꾸기 위해서 식의 부호를 조작했습니다.
Dij = -(-Ti * j + Ti * i - Vj)

(-Ti >= -Ti+1)

그래서 모든 (i, j) 쌍에 대해 -Ti * j + Ti * i - Vj 의 최소값을 구한뒤 음수를 취해서 답을 구하면 된다고 생각했고 i 가 정해지면 Ti와 i 가 정해지므로 i를 1씩 증가시키면서 j를 x로 생각하면 앞의 식이 i번째 직선의 방정식이 돼서 -Ti 를 기울기로, Ti * i 를 y 절편으로 생각하여 컨벡스헐 트릭을 사용하고 나온 결과값에 Vj 를 빼준 값으로 답을 갱신하였습니다. 물론 시간 제한 D가 있기 때문에 날짜가 D보다 많이 차이나는 직선은 그때 그때 앞에서 빼줬습니다.

그런데 실수연산과 deque 을 사용하여 구현했을때에는 30%정도에서 틀리길래 실수연산을 없애고 배열로 구현해봤는데 10% 정도? 에서 틀리네요.. 어디가 잘못된걸까요?

댓글을 작성하려면 로그인해야 합니다.