근수의 카드게임
면접 대비시간 제한1초메모리 제한1024 MB
매 턴 승형이가 1, 2, 3 카드 중 하나를 없애면 근수가 남은 카드 하나를 골라 S에 더한다. 둘 다 최선으로 두고, S가 K를 넘으면 -1이 된다.
문제
근수와 승형이는 '근수의 카드게임3'을 즐기고 있다. 근수의 목표는 최종 점수 를 최대화하는 것이고, 승형이의 목표는 를 최소화하는 것이다. 초기값은 이다. 게임은 총 턴 동안 진행되고 각 턴에는 다음 과정이 이루어진다.
- 세 장의 카드가 주어진다. 각 턴마다 , , 이 적힌 카드가 각각 한 장씩 주어진다.
- 승형이가 세 장의 카드 중 한 장을 제거한다.
- 근수가 남은 두 장의 카드 중 한 장을 골라 그 카드의 값을 에 더한다.
모든 턴이 끝난 뒤 최종 점수 가 를 초과하면 최종 점수 는 로 처리된다. 모든 정보는 모두에게 공개되어 있으며, 두 사람은 항상 최선의 전략으로 행동한다. 이때의 최종 점수 를 구하여라.
입력
첫째 줄에 진행할 게임의 턴 수 과 가 주어진다. (; )
출력
근수와 승형이가 항상 최선의 전략으로 게임을 진행하였을 때, 최종 목표치 값을 구하여라.