[백준] 20938. 반짝반짝

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

문제 요약

• 불이 들어온 전구 개수의 최대 기대값을 구해야함
• 전구가 일렬로 늘어서있음
• 한 전구가 꺼지면 오른쪽은 다 꺼짐
• 전구 스트립은 최대 K개 만큼 분할 가능하고(최대 10개), 분할된 전구는 독립적으로 작동

접근법

• DP 아이디어는 쉽게 떠올림
• 적당히 끊어서 기대값을 구하고, 나머지 구간에 대해서 최대 기대값을 구하는 방식
  • 1 // 2, 3, 4, ..., N
  • 1, 2 // 3, 4, ..., N
• 끊긴 곳의 기대값을 구하는 방법
  • O O X : 성공 성공 실패 * 2
  • O O O : 성공 성공 성공 * 3
• 그런대 기대값을 매번 구하면 시간 초과가 발생할 것임
• cache[s][e] 형태로 저장을 하고 싶은데...
• 앞에서 했던 것을 이용해야함
• 1개 일때
  • O
  • X
• 2개 일때
  • O O ==> 앞에서 했던 O 이용 가능
  • O X ==> 앞에서 했떤 O 이용 가능
  • X .. ==> 앞에서 했던 X를 그대로 사용
• 3개일때
  • O O O ==> "O O" 이용 가능
  • O O X ==> "O O" 이용 가능
  • O X .. ==> "O X" 그대로 사용
  • X ... ==> "X"를 그대로 사용

정리

• dp[a][b] : 0부터 a까지 b간을 나눴을때 최대 기대값
• dp[a][b] = max{dp[a - 1][b - 1] + cache[a][a], dp[a - 2][b - 1] + cache[a - 1][a], ....}
• 시간복잡도 ${O(N^2*K)}$
• 내가 구현한건 수행시간이 상당히 높았음. 어딘가 최적화할 곳이 있는듯