AOJ

압축을 해제하여 뒤집고 다시 압축을 진행하기엔 소요가 많으므로, 입력값을 직접적으로 이용하여 출력을 뽑아내도록 한다. 재귀적으로 깊게 탐색하는 것이 자명해 보인다.

처음 접했을 때, 굉장히 난해해 보이는 문제였다. 반복문만 돌리는 brute force만 써서는 시간초과가 날 것이 뻔해 어느정도의 재귀를 통해 구현하려 했다. 교재의 아이디어를 참고하여 내가 작성해본 코드는 다음과 같다.

완전 탐색시 시간초과 날 것이 자명하므로 DP를 수행하기로 하자

동적계획법 문제로 나온 문제이지만, 최대한 수학으로 간결하게 풀고 싶었다. 공식을 도출하는데 시간 소요가 컸다.

결정적으로 중요한 것은 데우는 시간이다. 도시락을 먹는 것은 동시에 다수가 할 수 있지만, 데우는 것은 반드시 하나씩 해야 하기 때문이다. 데우는 시간을 기준으로 도표를 그려보면 먹는 시간을 내림 차순으로 정렬하는 것이 가장 이상적인 경우임을 알 수 있다.