백준 10837번 동전 게임

문제 링크입니다: www.acmicpc.net/problem/10837

10837번: 동전 게임

문제의 규칙들을 잘 읽으면 무난하게 풀 수 있는 문제였습니다.

3개의 규칙들 중 핵심 내용은 아래와 같습니다.

1. 항상 영희가 먼저 던진다.

2. 한 명이 남은 기회에 모든 점수를 얻더라도 상대방이 현재까지 얻은 점수보다 작게 되면 게임 도중 어떤 시점에서도 게임은 바로 끝난다. 

 

C개의 M, N의 쌍이 주어질 때, (M, N)의 유형은 크게 세 가지입니다.

1. M과 N이 같을 경우

2. M이 N보다 클 경우 즉, 영희의 점수가 더 높을 경우

3. N이 M보다 클 경우 즉, 동수의 점수가 더 높을 경우

 

1번 유형의 경우 둘이 계속 똑같은 결과가 나올 경우 항상 100% 가능하다는 것은 자명합니다.

이제 남은 것은 2번과 3번 유형인데, 남은 라운드 수와 영희와 동수의 점수차를 통해 가능한지 여부를 아래와 같이 판별할 수 있습니다.

영희와 동수의 점수차를 남은 라운드 수 내에 메꿀 수 있다면 가능한 경우이고, 그렇지 않다면 불가능합니다.

정리를 하자면, 영희가 항상 동전을 먼저 던지기 때문에 영희의 점수가 높을 경우 최대 2점 더 높을 수 있고, 동수의 점수가 높을 경우에는 최대 1점 더 높을 수 있습니다.

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~