2024. 6. 1. 13:52ㆍIT/BaekJoon
문제 링크
https://www.acmicpc.net/problem/1072
문제
김형택은 지금 몰래 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
통과한 답안
namespace _1072
{
internal class Program
{
static void Main(string[] args)
{
string[] inputs = Console.ReadLine().Split(' ');
long X = long.Parse(inputs[0]);
long Y = long.Parse(inputs[1]);
long Z = 100 * Y / X;
if (Z >= 99)
{
Console.WriteLine(-1);
return;
}
long left = 1;
long right = 1000000000;
long games = -1;
while (left <= right)
{
long mid = (right + left) / 2;
long newCnt = X + mid;
long newWin = Y + mid;
long newRate = 100 * newWin / newCnt;
if (newRate > Z)
{
games = mid;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
Console.WriteLine(games);
}
}
}
현재 게임 횟수와 이긴 횟수가 주어지고 현재 승률을 정수 Z로 저장한 뒤
새로운 게임 횟수가 주어졌을 때, 승률이 변하는 경우에 필요한 최소 게임 수를 묻는 문제이다.
(단 새로운 게임은 모두 승리한다고 한다, 승률이 바뀌지 않는 경우에는 -1을 출력한다)
현재 게임 수는 X이고 이긴 횟수는 Y이므로
승률 Z는 100 * Y / X 로 표기할 수 있다.
우선 승률이 바뀌지 않는 경우를 찾아보면,
승률이 99% 이상인 경우에는 아무리 게임을 추가해도 승률이 바뀌지 않으므로,
승률을 구한 뒤에 Z가 99 이상인 경우에는 -1을 출력하고 종료되도록 한다.
이후에 승률이 변하는 경우를 구하면,
새로운 게임의 수를 c로 한다면
새로운 승률 newRate = 100 * (Y + c) / (X + c)가 된다.
이 값이 Z보다 큰 경우, 승률이 바뀌게 된 것이다.
따라서 이를 간단하게 구현하면 아래와 같이 구현할 수 있다.
int games = 0;
for (int i = 1; ; i++)
{
long gameCnt = X + i;
long winCnt = Y + i;
long newRate = 100 * winCnt / gameCnt;
if (newRate > Z)
{
games = i;
break;
}
}
하지만 이 경우에는 조건에 따라서 시간이 너무 오래 걸릴 수 있으므로
계산을 빠르게 작동하도록 코드를 수정해야한다.
이러한 조건에 맞는 결과를 찾는 경우에 개선할 수 있는 방법으로 이분 탐색을 적용할 수 있다.
위의 새로운 게임 수를 찾는 과정에서 for 문을 이용하여 1부터 찾았다면,
아래처럼 1부터 X의 최대 범위를 지정한 후에 이분 탐색을 적용하면 빠르게 해결할 수 있다.
long left = 1;
long right = 1000000000;
long games = -1;
while (left <= right)
{
long mid = (right + left) / 2;
long newCnt = X + mid;
long newWin = Y + mid;
long newRate = 100 * newWin / newCnt;
if (newRate > Z)
{
games = mid;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
최솟값과 최댓값을 지정한 후에 이들의 중간값을 이용하여
승률이 변하는 최소의 게임 수를 구할 수 있다.
'IT > BaekJoon' 카테고리의 다른 글
[BAEKJOON] 백준 1270: 전쟁 - 땅따먹기 (C#) (0) | 2024.06.01 |
---|---|
[BAEKJOON] 백준 1166: 선물 (C#) (0) | 2024.06.01 |
[BAEKJOON] 백준 1063: 킹 (C#) (0) | 2024.06.01 |
[BAEKJOON] 백준 1002: 터렛 (C#) (0) | 2024.05.31 |
[BAEKJOON] 백준 1244: 스위치 켜고 끄기 (C#) (0) | 2024.05.31 |