Editorial

---

1799D1

summary: cpu 두개가 있는데, 두 cpu를 사용해서 프로그램을 정해진 순서대로 실행시켜야 한다. 어떤 cpu가 마지막으로 실행한 프로그램과 그 다음 실행할 프로그램이 같으면 $hot_i$, 다르면 $cold_i$만큼 시간이 걸린다.

모든 프로그램을 실행시키는 데 걸리는 시간 합의 최솟값을 구하는 문제이다.

solution:

$dp_i$: 한 cpu는 프로그램 $i$, 한 cpu는 다른 어떤 프로그램을 돌렸을 때 이때까지 구한 최솟값으로 정의한다. (초기값=$inf$)

현재 돌려야 할 프로그램을 $x$, 직전에 돌린 프로그램을(순서상 하나 전) $y$라고 하자.

그리고 나서 $ndp$를 정의해서 값을 갱신시킨 뒤 $dp$에 덮어씌울 것이다. (초기값:$inf$)

$x=y$일 경우

$x$를 제외한 모든 $i$에 대해, cpu는 $(x,i)$상태일 것이다. 이미 모든 $dp_i$의 상태는 $x$를 포함하므로,

$ndp_i=min(ndp_i, dp_i+hot_i)$

$ndp_x=min(ndp_x,dp_i+hot_i)$

$x\neq y$일 경우

모든 $i$에 대해, cpu는 $(y,i)$일 것이다.

$ndp_i=min(ndp_i, dp_i+cold_x)$

$ndp_y=min(ndp_y, dp_i+cold_x)$ : cpu가 $(y,i),i \neq x$였을 경우

$ndp_y=min(ndp_y, dp_x+hot_x)$ : cpu가 $(y,x)$였을 경우

와 같이 하면 $O(nk)$의 시간복잡도로 해결된다.