글 읽기 - 1072번 게임 질문있습니다.

bch8623 5년 전 0

이 문제는 완전탐색으로 해결할려고 시도하다가 TLE가 떴습니다.

그래서 다른사람이 작성한 코드를 보고 학습하는 도중에 AC된 다른 사람 코드보고 이해가 안되는 점이 한 가지 있어서 질문합니다.

이분탐색으로 문제를 해결한 것 같습니다. x와 y에 mid를 증가시킨 상태에서 변경된 Z값을 따져서 [left,right] 구간을 변경하고 있는데요.

만약에 , mid가 Z값이 변하는 구간이라면 right 를 mid-1로 바꾸게 되면 변경된 [left,right] 구간에서는 Z가 증가하지 않지 않나요?

제가 잘못한 것인지는 모르겠지만 혹시나 해서 질문을 해봅니다.

#include <iostream>
#include <cstdio>
 
#define MAX_INF     1000000000
using namespace std;
 
long long x, y, z;
 
int main(int argc, char const *argv[]) {
  long long l, r, mid;
  while(cin >> x >> y) {
    long long temp_z = 0;
    z = 100 * y / x;
    l = 0;
    r = MAX_INF;
 
    if (z >= 99) {
      cout << "-1" << "\n";
    }
 
    else {
      // 시간 초과를 해결하기 위해 이분 탐색.
      while (l <= r) {
        mid = (l + r) / 2;
        temp_z = 100 * (y+mid) / (x+mid);
        if (z < temp_z) {
          r = mid - 1;
        }
        else
          l = mid + 1;
      }
      cout << l << "\n";
    }
  }
  return 0;
}

rhs0266 5년 전 0

(a+x)/(b+x) 값을 x의 크기에 따라 생각해보면,

x가 커질수록 값이 커지고, x가 작아질수록 값도 작아집니다.

질문하신 부분대로, r이 작아지면 다음의 mid도 같이 작아지므로 바뀔 Z도 작아질 것으로 보입니다.

bch8623 5년 전 1

이해가 됬습니다. 감사합니다 ! :D

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1072번 게임 질문있습니다.

bch8623 5년 전 0

rhs0266 5년 전 0

bch8623 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말