백준 1072 게임 C++ 풀이

✅ 백준 1072 게임 C++

🔷 문제 설명

문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있습니다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었습니다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했습니다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰습니다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았습니다.

이제 형택이는 앞으로의 모든 게임에서 지지 않습니다. 하지만, 형택이는 게임 기록을 삭제할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했습니다.

게임 기록은 다음과 같이 생겼습니다.

• 게임 횟수: \(X\)
• 이긴 게임: \(Y\) (\(Z\%\))

\(Z\)는 형택이의 승률이고, 소수점은 버립니다. 예를 들어, \(X=53\), \(Y=47\)이라면, \(Z=88\)입니다. \(X\)와 \(Y\)가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 \(Z\)가 변하는지를 구하는 프로그램을 작성하시오.

테스트케이스

✅ 케이스 1

입력:

100 80

출력:

6

✅ 케이스 2

입력:

10 8

출력:

1

✅ 케이스 3

입력:

1000000000 999999999

출력:

-1

문제설명

• 현재 게임 횟수가 \(X=100\), 이긴 게임이 \(Y=80\)이라면 승률은 \(80\%\)입니다. 여기서 한 판을 더 이기면 \(\frac{81}{101} \approx 80.198\), 소수점 아래를 버리면 여전히 \(80\%\)라서 승률이 오르지 않습니다.
• 두 판, 세 판, 네 판, 다섯 판을 더 이겨도 승률은 \(80\%\)로 유지됩니다.
• 여섯 판을 더 이기면 \(\frac{86}{106} \approx 81.132\), 소수점을 버려도 \(81\%\)가 되어 승률이 변합니다.
• 반면에 \(X=10\), \(Y=8\)인 경우에는 현재 승률이 \(80\%\)인데, 한 판만 더 이기면 \(\frac{9}{11} \approx 81.818\)로 \(81\%\)가 되어 바로 승률이 오릅니다.
• 그러나 \(X=1,000,000,000\), \(Y=999,999,999\)인 경우처럼 이미 승률이 \(99\%\)라면 아무리 많은 게임을 더 이겨도 \(100\%\)가 될 수 없고, 따라서 정답은 -1이 됩니다.
• 요약하면 승률이 오르는 최소 시점을 찾는 문제이며, 소수점 아래를 버리기 때문에 작은 이득으로는 승률이 오르지 않는다는 점이 핵심입니다. 승률이 \(99\%\) 이상이면 불가능한 경우도 있으니 주의해야 합니다.

🔷 아이디어

이분탐색을 사용

이분탐색은 값이 정렬되어 있는 경우에 적절한 알고리즘입니다. 정렬된 데이터에서는 중간값과 찾고자 하는 값을 비교해, 범위를 절반씩 줄여가며 원하는 값을 빠르게 찾을 수 있습니다.

예를 들어, 아래와 같이 오름차순으로 정렬된 배열에서 2를 찾는다고 가정합니다.

{1, 2, 3, 4, 5, 6, 7}

첫 번째 중간값:

{1, 2, 3}  |  {4}  |  {5, 6, 7}

중간값 4를 확인합니다. 2 < 4이므로 왼쪽 범위로 좁힙니다.

다음 단계:

{1}  |  {2}  |  {3}

중간값 2를 확인합니다. 찾고자 하는 값과 같으므로 탐색을 종료합니다.

그러나 정렬되어 있지 않은 경우에는 이분탐색이 불가능합니다. 예를 들어, 아래와 같이 배열이 섞여 있을 때 5를 찾는다고 하면 다음과 같습니다.

{1, 2, 4, 3, 6, 5, 7}

반으로 나누면:

{1, 2, 4}  |  {3}  |  {6, 5, 7}

여기서 중간값 3을 확인했지만, 5가 왼쪽에 있는지 오른쪽에 있는지 알 수 없습니다. 정렬되어 있지 않기 때문에 탐색 방향을 결정할 수 없어, 이분탐색이 적합하지 않습니다.

이 문제에 적용

이 문제의 경우, 승률의 변화는 정렬된 것과 유사합니다. 작은 \(n\)일 때는 승률이 변하지 않고(No), 일정 시점 이후부터는 승률이 상승해(Yes) 계속 유지됩니다. 즉, 아래처럼 배열이 정렬된 것과 동일한 구조를 가집니다.

{No, No, No, Yes, Yes, Yes, Yes}

추가 게임 수 \(n\)	승률 (계산값)	변화
\(1\)	\(80.198\%\)	No
\(2\)	\(80.392\%\)	No
\(3\)	\(80.583\%\)	No
\(4\)	\(80.769\%\)	No
\(5\)	\(80.952\%\)	No
\(6\)	\(81.132\%\)	Yes
\(7\)	\(81.308\%\)	Yes
\(8\)	\(81.481\%\)	Yes

이처럼 정렬된 배열처럼 작동하기 때문에, 중간값에서 승률을 확인해 \(Z+1\) 이상이면 왼쪽으로, 아니면 오른쪽으로 범위를 절반씩 줄이면서 탐색할 수 있습니다.

• 이는 정렬된 배열의 효과를 가지기 때문에 이분탐색이 적절합니다.
• 범위를 반씩 줄여가며 탐색하면 \(O(\log_2 N)\)의 효율로 승률이 바뀌는 최소 지점을 찾을 수 있습니다.

🔷 구체적 풀이

문제 상황 정리

• 현재 게임 수: \(X = 100\)
• 현재 이긴 게임 수: \(Y = 58\)
• 현재 승률: \(Z = \lfloor \frac{Y}{X} \times 100 \rfloor = 58\)

목표: 승률이 \(Z+1 = 59\) 이상이 되는 최소의 \(mid\)를 찾는다.

앞으로 더할 게임 수를 1부터 \(10^9\)까지 배열처럼 생각합니다. 배열의 각 원소는 \(mid\)입니다.

[ 1   2   3   4   …   mid   …   right=1e9 ]

우리는 이 배열에서 \(mid\)를 선택해 다음 식을 계산합니다:

\[ \text{new}_Z(mid) = \lfloor \frac{Y + mid}{X + mid} \times 100 \rfloor \]

그리고 \(\text{new}_Z(mid) > Z\)가 되는 최초의 \(mid\)를 찾아야 합니다.

초기화

탐색 범위를 이렇게 설정합니다:

left = 1
right = 1_000_000_000
answer = -1
    

여기서 \(left\)는 배열의 첫 번째 칸, \(right\)는 배열의 끝 칸을 가리킵니다. \(answer\)는 승률이 올라가는 \(mid\)를 발견할 때마다 갱신합니다.

탐색 과정

1단계: 첫 \(mid\) 계산

배열 범위:

[ 1                              500,000,000                            1,000,000,000 ]
  ↑                                    ↑                                       ↑
 left                                 mid                                     right

\(mid = (1 + 1,000,000,000) // 2 = 500,000,000\)

승률 계산:

\[ \text{new}_Z(500,000,000) = \lfloor \frac{58+500,000,000}{100+500,000,000} \times 100 \rfloor = 99 \]

new_Z > Z → 승률이 이미 올랐음. 하지만 더 작은 \(mid\)에서도 승률이 오를 수 있으니:

• \(answer = 500,000,000\)
• \(right = mid - 1 = 499,999,999\)

2단계: 두 번째 \(mid\) 계산

배열 범위:

[ 1               250,000,000                   499,999,999 ]
  ↑                      ↑                             ↑
 left                   mid                           right

\(mid = (1 + 499,999,999) // 2 = 250,000,000\)

승률 계산:

\[ \text{new}_Z(250,000,000) = 99 \]

new_Z > Z → 더 작은 \(mid\)를 확인:

• \(answer = 250,000,000\)
• \(right = mid - 1 = 249,999,999\)

3단계: 세 번째 \(mid\) 계산

배열 범위:

[ 1         125,000,000         249,999,999 ]
  ↑                ↑                     ↑
 left             mid                   right

\(mid = (1 + 249,999,999) // 2 = 125,000,000\)

승률 계산:

\[ \text{new}_Z(125,000,000) = 99 \]

new_Z > Z → 더 작은 \(mid\)를 확인:

• \(answer = 125,000,000\)
• \(right = mid - 1 = 124,999,999\)

반복

이 과정을 반복하며 \(mid\)를 절반씩 줄여가며 탐색합니다.

• \(mid\)에서 승률이 \(> Z\)이면 더 작은 \(mid\)를 확인하고 \(answer\)를 갱신합니다.
• \(mid\)에서 승률이 \(= Z\)이면 더 큰 \(mid\)를 확인합니다.

근처 세밀한 탐색

이제 탐색이 좁혀져 \(left = 1\), \(right = 5\) 근처까지 왔다고 가정합니다.

[ 1           2           3           4           5 ]
↑                       ↑                       ↑
left                  mid                     right

1️⃣ \(mid = 3\)

\(mid = (1+5)//2 = 3\)

승률 계산:

\[ \text{new}_Z(3) = \lfloor \frac{58+3}{100+3} \times 100 \rfloor = 59 \]

new_Z ≥ 59 → 승률이 올랐음:

• \(answer = 3\)
• \(right = mid -1 = 2\)

2️⃣ \(mid = 1\)

이제 \(left=1\), \(right=2\)

\(mid = (1+2)//2 =1\)

승률 계산:

\[ \text{new}_Z(1) = \lfloor \frac{58+1}{100+1} \times 100 \rfloor =58 \]

new_Z = 58 → 아직 안 올랐음:

• \(left = mid+1 = 2\)

3️⃣ \(mid = 2\)

이제 \(left=2\), \(right=2\)

\(mid=2\)

승률 계산:

\[ \text{new}_Z(2) = \lfloor \frac{58+2}{100+2} \times 100 \rfloor =58 \]

new_Z = 58 → 아직 안 올랐음:

• \(left = mid+1 =3\)

종료

이제 \(left=3\), \(right=2\), 즉 \(left>right\)

탐색 종료. 지금까지 갱신된 \(answer=3\)이 최소값으로 결정됩니다.

🔷 전체코드

#include <iostream>

using namespace std;

int main(void)
{
    long long X,Y,Z;
    cin>>X>>Y;
    Z=Y*100/X;
    
    long long left=0,right=1000000000;
    long long mid=0,ans,answer=-1;
    if(Z>=99)
    {
        cout<<-1<<endl;
        return 0;
    }
    while(left<=right)
    {
        mid=(left+right)/2;
        ans=((Y+mid)*100 )/ (mid+X);
        
        if(ans>Z)
        {
            right=mid-1;
            answer=mid;
        }
        else
            left=mid +1;
    }
    cout<<answer<<endl;
    
    return 0;
}