[BOJ] 5135번 Ice Cream

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

 

풀이

$t+s>2d$ 또는 $t+s≤2d$ 라는 점에 주의해야 한다.

 

$cost(i)$를 $i$개의 scoop의 최소 비용이라 하자.

$cost(0) = 0$

$cost(1) = s$

$cost(2) = d$

$cost(3) = t$

$cost(4) = min(s+t, 2d)$

$cost(5) = d+t$

$cost(i+3) = cost(i)+t\ (i\ge 3)$

 

 

바닐라 아이스크림만 원하는 사람들의 scoop의 합을 $v_1$, 초코 아이스크림만 원하는 사람들의 scoop의 합을 $c_1$, 둘 다 원하는 사람들의 scoop의 합을 $v_2$, $c_2$라고 하자.

 

$ans = 0$

$v_1$이 6 미만이 될 때까지 3을 빼면서 $ans$에 $t$를 더한다.

$c_1$, $v_2$, $c_2$도 같은 방법으로 6 미만으로 만든다.

 

최소 비용은 다음과 같다.

$ ans+\min\limits_{\substack{0\le i\le v_2\\0\le j\le c_2}}(cost(v_1+i)+cost(c_1+j)+cost(v_2-i+c_2-j)) $