BOJ 14243 - 출근 기록 2
대부분의(?) 경우를 모두 처리해준다.
이제 $b$와 $c$를 모두 쓸 수 있는 상황에 어떻게 결정할지 생각해보자.
남은 $a,b,c$의 개수를 $A,B,C$라 하고 남은 채워야할 길이를 $R$이라고 할 때
$R-2B+1$ 이 $R-3C+2$ 보다 더 작다면 $b$를 먼저 붙이고 아니면 $c$를 먼저 붙인다.
이 수는 남은 길이에 대해 $B$를 모두 채우기 위해 필요한 공간을 제외하고 남은 공간과 $C$도 마찬가지로 구해준것이다.
이렇게 그리디하게 계속 결정하면 된다.
Comments