체감티어: G5 태그: 냅색, dp, 브루트포스 제 1회 임스의 메이플컵의 C번이다. 냅색은 구원자이다. 일단 n명중 m명을 뽑아 15분간 보스를 잡고 m명이 얻은 값을 최대화 하면 되는 간단한 문제이다. 뭔가 dp냄새가 난다. 하지만 테이블을 어떻게 잡아야 할지 잘 모르겠다. 일단 15분은 900초이므로 900칸의 배열을 생성하면 준비는 끝난다. 문제는 각 캐릭터마다 초당 데미지가 다르다. 하지만 보스의 체력과 초당 데미지 사이에 관계를 Wi로 보고, 보스를 잡고 주는 값을 Ci로 보면 단순한 냅색의 형태가 나온다. i번째 보스를 잡는데 걸리는 시간은 (보스의 체력 / 초당 데미지)의 올림으로 나타낼 수 있다. 이를 각 캐릭터마다 따로 적용하고 냅색을 한 결과의 합을 구하면 된다. 더보기 #define..