BOJ 14243 - 출근 기록 2

June 11, 2023

대부분의(?) 경우를 모두 처리해준다.

이제 $b$ 와 $c$ 를 모두 쓸 수 있는 상황에 어떻게 결정할지 생각해보자.

남은 $a,b,c$ 의 개수를 $A,B,C$ 라 하고 남은 채워야할 길이를 $R$ 이라고 할 때

$R-2B+1$ 이 $R-3C+2$ 보다 더 작다면 $b$ 를 먼저 붙이고 아니면 $c$ 를 먼저 붙인다.

이 수는 남은 길이에 대해 $B$ 를 모두 채우기 위해 필요한 공간을 제외하고 남은 공간과 $C$ 도 마찬가지로 구해준것이다.

이렇게 그리디하게 계속 결정하면 된다.

You may also enjoy