6-G 질문있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

6-G

해결된 질문

작성

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

아래 코드가 틀렸다고 나오는데
ll r = 1e18 + 4;
이 부분 코드를 1e9로 바꿔서 제출하기만 하면 맞다고 나옵니다. 상한선을 저번에 풀었던 드래곤 앤 던전 문제처럼 크게 잡았는데 왜 문제가 생겼는지 모르겠습니다.

시간초과가 나온거면 이해가 가는데 왜 틀렸다고 나오는지 이해가 안가네요..

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll x, y, z, mid, ret;

bool check(ll mid) {
    ll new_z = (y + mid) * 100 / (x + mid); // 새로운 승률
    return new_z > z; // 기존 승률과 비교
}

int main() {
    cin >> x >> y;

    ll l = 1; 
    ll r = 1e18 + 4; // 최대 범위를 현실적으로 설정
    z = y * 100 / x; // 기존 승률
    ret = 0;

    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) { // 승률이 증가하는 경우
            ret = mid;
            r = mid - 1; // 더 작은 mid 값을 탐색
        }
        else { // 승률이 증가하지 않는 경우
            l = mid + 1; // 더 큰 mid 값을 탐색
        }
    }

    if (ret == 0) cout << -1;
    else cout << ret << "\n";

    return 0;
}

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 16님 ㅎㅎ

bool check(ll mid) {
    ll new_z = (y + mid) * 100 / (x + mid); // 새로운 승률
    return new_z > z; // 기존 승률과 비교
}

이부분에서 mid = 1e18 / 2일 수가 있고 여기에다가 * 100을 하게 되면 -> 오버플로우가 발생 -> 틀렸다고 뜨는 것 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

16wjdekdms님의 질문에 대해 설명 드리겠습니다!

이 문제와 관련하여 제기된 상황은 연산 중에 활용되는 자료형 범위와 오버플로우 가능성입니다. ll r = 1e18 + 4;와 같은 큰 값을 상한선으로 설정했을 때, 이는 오버플로우가 발생하거나 불필요한 계산을 통해 결과값에 영향을 줄 수 있습니다.

문제의 원인:

자료형의 한계: long long 자료형은 일반적으로 64비트를 제공하며, 이는 약 9.223 x 10^18까지의 값을 저장할 수 있습니다. 1e18 + 4와 같은 값은 범위 내에 있지만, 계산 과정에서 중간값 mid가 증가하면서 오버플로우가 발생할 가능성이 존재합니다.
불필요한 계산: 큰 값의 상한선은 이진 탐색 수행 때 불필요한 계산을 증가시킬 수 있습니다. 이는 오히려 틀렸다고 나올 가능성을 증가시키며, 작은 범위 내에서는 결과가 정확하게 나온다는 것을 의미합니다.

다음 링크에서 유사 문제를 해결하는데 도움이 되는 자료를 확인할 수 있습니다:
- 6-G 반례 질문 - 비슷한 문제를 다루며, 작은 값에서 정답으로 채점되고 큰 값에서 오답이 나오는 경우가 설명되어 있습니다.

6-G 자료형 질문 - 자료형의 범위와 소수점 계산에 대한 고려가 필요한 경우의 설명이 포함되어 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.

현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

6-G 질문있습니다.