79brue의 PS 블로그

다이아 2 초반은 나름 순조로웠다. 하지만 뒤로 갈수록 남은 문제들이 심상치 않아졌다. 현재 다4-다2권에는 15문제가 남아 있다. 남은 문제: 50 → 46문제BOJ 27355. PathsTL이 0.3초라는 게 특이할 만한 문제이다. 문제 풀이 자체는 꽤나 자명한 편이다. 플로우 모델링 비슷한 걸 해 보면 결국 계속 등장하는 볼록성 있는 그리디라는 것을 알 수 있다. 그래서 루트가 고정되어 있다면 그리디하게 가장 긴 경로를 뽑는 것을 반복해 풀 수 있다. 여기까지만 알아도 마지막 섭테 제외하고 전부 어렵지 않게 풀 수 있다. 문제는 마지막 서브태스크이다. 일단 TL이 다른 문제처럼 정상적인 범주 (2초 정도) 에 있다고 가정하고 풀어 보자. 루트 하나에 대해서 dp의 형태로 답을 구하려면 가장 쉽게 생..