79brue의 PS 블로그

JOISC 문제 몇 개를 땅따먹기에서 풀어 보았다. BOJ 24137. 塗り箸 (Chopsticks)옛날 NYPC의 어떤 output only와 상당히 비슷해 보이는 문제이다. 형태를 봤을 때 구간 DP로 진행하는 것이 가장 좋아 보인다. 어떤 구간 $[l, r]$에 대해 최소 비용으로 칠하는 방법을 구한다고 생각해 보자. 먼저 이 구간 전체에 색칠할 색 $c$를 정한다. 다음으로 이 위에 덮어쓸 구간을 정한다. 모든 $c$에 대한 최소 비용을 $[l, r]$에 대한 최소 비용으로 정한다. 이렇게 하면 $O(N^3)$ 풀이가 나온다. 상수가 $52/6$ 정도로 다소 커서 걱정되지만, 짜 보면 문제없이 통과된다.#include using namespace std;typedef long long ll;int..