https://www.acmicpc.net/problem/1072
1072번: 게임
김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시
www.acmicpc.net
문제
김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.
이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.
게임 기록은 다음과 같이 생겼다.
- 게임 횟수 : X
- 이긴 게임 : Y (Z%)
- Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.
X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.
입력
각 줄에 정수 X와 Y가 주어진다.
출력
첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.
제한
- 1 ≤ X ≤ 1,000,000,000
- 0 ≤ Y ≤ X
풀이
이 문제는 분명 알고리즘 분류로는 이분탐색으로 들어갔으나.... 정신 차리고 보니 수학으로 풀고 있었습니다.
어릴 때 이런 문제 수학 책에서 몇번 본 듯한 기분이 나는 문제 입니다.
그냥 문제에 주어진대로 식을 유도하면 몇 판 더 해야하는지를 나타내는 a 값에 대해서 위와 같은 식이 나타납니다.
여기서 중요한 것은 저식이 소수점 자리없이 나누어 떨어진다면 그 숫자가 그대로 답이 되는 것이고,
나누어 떨어지지 않는다면 그것이 그대로 답이 될 수 는 없다는 것입니다.
이 문제에서는 정수형을 사용하기 때문에 소수점 아래가 버려질 수 밖에 없습니다.
그런데 나누어 떨어지지 않는다면 a역시 소수점 아래가 버려지게 되겠죠.
그렇게 구해진 a는 z가 1 커지기 위해 필요한 숫자보다 사소하지만 0.xxxx만큼 작을 수 밖에 없습니다. 이러면 z를 1증가 시킬 수 있는 수가 될 수 없겠죠. 따라서 1을 더해주는 겁니다!!!
그리고 기존의 승률이 이미 99이상이라면 더이상 증가할 수가 없습니다.
100인 경우야 당연하고, 99인 경우 아무리 플레이를 여러번 더해도 100이 될 수는 없어 이 경우는 -1을 출력해주면 됩니다.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main (void) {
long long x, y;
long long z, result, re;
scanf("%lld %lld", &x, &y);
z = (100*y)/x;
if(z >= 99){
printf("-1\n");
return 0;
}
re = (100*y-z*x-x) % (z-99);
result = (100*y-z*x-x) / (z-99);
if(re == 0){
printf("%lld\n", result);
}
else{
printf("%lld\n", result+1);
}
}