[백준(BOJ)] 1072번 : 게임 - C++[CPP]

https://www.acmicpc.net/problem/1072

1072번: 게임

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 수학
• 이분 탐색

 

---

 

⊙ 문제 접근 과정

 

문제를 보자마자 무지성으로 코드를 단순하게 짜 봤다. 그리고 시간 초과가 떴다. ㅎ

 

시간 초과를 본 후 자연스럽게 투 포인터 알고리즘을 적용시켜 시간 초과를 해결했다.

 

※주의사항

   99%는 아무리 해도 100%가 되지 않는다.

---

 

⊙ 문제 풀이(시간 초과 코드)

 

#include <iostream>

using namespace std;

long long X, Y, Z;
int cnt=0;

int main() {
    cin >> X >> Y;
    Z=(Y*100/X);
    int temp=Z;
    
    if(Z>=99) {
        cnt=-1;
    } else {
        while(temp!=Z+1) {
            X++; Y++; cnt++;

            temp=(Y*100)/X;
        }
    }

    cout << cnt;
}

 

⊙ 문제 풀이(정답 코드)

 

#include <iostream>

using namespace std;
#define MAX 1000000000

long long X, Y, Z;
int cnt=-1;

int main() {
    cin >> X >> Y;
    Z=(Y*100/X);
    
    if(Z>=99) {
        cout << cnt;
        return 0;
    } 

    int left=0, right= MAX;

    while(left<=right) {
        int mid=(left+right)/2;
        int temp=(Y+mid) * 100 / (X+mid);

        if(Z<temp) right=mid-1;
        else left=mid+1;
    }
    
    cout << left;
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!