[ICPC 본선 대비 뇌셋] Day 19

백준 2427번 2012 지구 멸망 www.acmicpc.net/problem/2427

2427번: 2012 지구 멸망

V가 i번, P가 j번 사용 될 때 가능한 최대 횟수가 얼마일지를 구해준 다음 이를 이용해서 최소 시간을 구해주면 된다.

dp식은 다음과 같다.

$dp[i][j] = max(dp[i][j], dp[i-1][k]*(j-k))$ for{k=j-2 ; k>= max(j-2050, 0) ; k--}

dp가 왜 성립하는지에 대한 정당화가 필요하지만 개인적으로 다이아3 정도는 아닌 듯 하다.

[증명] bottom top으로 증명하려다보면 잘 막힌다. top bottom으로 생각하자.

먼저 dp[i][j]는 i, j가 증가함에 따라 자명히 증가한다.

dp[i][j]를 구할 때, 마지막 회의의 사람이 j-k명 남아있다고 가정하자. 그러면 j-k명 각각이 뽑힌 그룹들은 P와 V가 각각 많아야 k번, i-1번 쓰여야한다. dp[i][j]의 증가성에 의해 각 그룹의 사람수는 최대 dp[i-1][k]명. 따라서

dp[i][j] = max(dp[i-1][k])*(k-j), dp[i][j])가 성립한다.

이 때 j의 범위를 제한해주는것이 필요한데, 이는 P, V의 제한이 1000임을 통해서 커봐야 k-j<=2004라는 것을 알 수 있다.

짜면 된다.