https://www.acmicpc.net/problem/31929
문제요약
- 승/패 정보가 주어짐(j번째 시행시 얻는/잃는 점수)
- 패배할때 잃는 점수 조건이 있음 : a * K + b에서 최대 b만큼 점수를 잃음
- 쉽게 말해서 패배할때 점수의 K 나머지만큼 최대로 점수를 잃음
- 나머지가 0이면 조건이 성립하지 않고
- 최대로 얻을 수 있는 점수 구하기
접근법
- 처음에는 뭔가 했음
- 승/패 순서는 정해져있음 => j번째 시행할때 얻는/잃는 점수가 정해져 있음
- 승을 x만큼, 패를 y만큼 진행했을때 경기를 한다면??
- 승을 x만큼, 패를 y만큼 진행할때 얻을 수 있는 뭔가가 있을 것 같음 => DP
- 그런데 패배 조건이 걸림. 나머지때문에 영향을 주지 않을까?
- 나머지에 따라서 패배 점수에 영향을 주니까, "역전" 같은게 있지 않을까?
- 점수 1 : K * N + (K - 1)
- 점수 2 : K * (N - 1) + (K - 1)
- 점수 1에서 최대로 점수를 잃으면 => K * N
- 점수 2에서 최소로 점수를 잃으면 => K (N - 1) + (K - 1) = K N - 1
- 아무리 해도 점수1 > 점수2
- 즉 나머지때문에 패배할때 역전할 일은 없음
- 승리/패배 모두 점수가 높은 것이 유리
- 즉 현재상태[승][패] = max{이전상태[승 - 1][패] + 승, 이전상태[승][패-1] - 패}, 단 패배 연산은 조건에서 주어진대로 수행
newbieski