[백준] 21321. 클레이 사격 게임

https://www.acmicpc.net/problem/21321

요약

• 클레이를 맞춰서 최대의 점수를 얻어야함
• 클레이마다 주기와 점수가 있음
• 1 ~ N 번 위치 클레이가 있음 : 낮은 클레이를 맞추면 그 위 클레이는 못맞춤, 주기가 겹치면 아래 클레이만 맞추게됨
• 라운드 * 점수 만큼 점수를 얻음

접근법

• 주기를 어떻게 처리할지 처음에 아이디어를 떠올리기 힘들었음
• 1번 클레이부터 살펴보면, 1번클레이에 배수가 되는 클레이들은 어찌되었든 1번이 제거되어야 이후 진행이 가능함
• 2, 3... 도 마찬가지임 => 클레이마다 선후관계 파악 가능
• 위상정렬을 해야하나 생각했었으나 그렇게는 안함
• 클레이가 처리된 상태를 비트로 표현함 + dp로 접근함
• 어떤 bit가 주어진다면
  • dp[bit] : 1로 마스킹된 클레이들이 처리되었을때의 최대 점수
  • 바로 이전 상태를 파악해 볼 수 있음. 무슨 말이냐면 예를들어 7번 클레이가 마스킹되었을때, 마지막 순서에 7번클레이가 처리되었다고 볼 수 있음 즉
  • (bit에서 7번을 unmasking한 상태) -> 7번클레이격파 -> (bit)
  • 그리고 7번 클레이가 격파되기 위해서 2, 3, 5가 격파되어야한다고 가정하면, bit에서 2,3,5가 처리되었는지 확인 가능함
  • 그리고 이 때의 값은 dp[(bit에서 7번을 unmasking한 상태)] + 7번점수 * 라운드 값
  • 모든 클레이에 대해서 값을 구하고 max를 구할 수 있음
• 주의할 점은 절대로 만들어 질 수 없는 상태에 대해서는 별도의 체크를 해줘야함.
• 최종 구하는 값은 dp[111...111]임
  • ${max(dp[0111..111_{(2)}] + b[1]*n, dp[101...111_{(2)}] + b[2] * n, ....}$