BOJ 4786 Cosmocraft

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

풀 때 도움 되는 몇가지 사실.
0. 표기: worker 수를 W, production 수를 P, 그 턴에서 적 수를 A

1. P랑 W의 관계를 파악하기 위해서 일단 모든 A를 0으로 가정할게요.

2. 각 턴에서 만들 수 있는 최대 army는 min(P,W)에요.

3. 마지막 두 턴에서 최대로 만들 수 있는 army의 수는 마지막 2번째에서 P,W를 기준으로 항상 min(P,W)+W에요. 증명은 케이스 나눠서 하면 돼요

4. 그러면 결국 마지막에서 3번째 턴까지 min(P,W) + W를 최대화 시키는게 목표가 되는데 여기서 그리디가 들어가요.
생각하기 쉬운게
P가 W보다 클 경우 W를 2배하고
W가 P보다 클 경우 돈을 P를 W로 키우는데 쓰고 나머지는 W를 키운다는 전략

- W가 크면 클 수록 돈이 많이 쌓이니까 이득임. 이제 어느정도 P를 같이 키워야 최대 이득이냐가 관건인데, 이 전략 자체가 자명하지는 않으므로 증명이 필요합니다,

저 전략에 합의가 되면 A는 거들 뿐? 이기 때문에
이제 P랑 W에 쓸 돈을 조금씩 army를 만드는데 배부해서 A를 제거해줘야 해요

5. 이제 army를 미리 만들어놓는 것은 오직 다음 턴에만 쓸모가 있어요. 2턴 이상 지나갈 경우 그냥 그 직전 턴에 만드는게 이득이기 때문에요

6. 따라서 우리가 고려해줘야할 케이스는
(1)다음 턴까지 살아남을 수 없는 경우
(2)다음 턴에 army를 빌려줘야 하는 경우
(3) 다음 턴에 army를 빌려주지 않아도 되는 경우
가 돼서, 각 케이스를 풀면 돼요

4에서 이러한 그리디가 성립하는 이유는 무엇일까?