99클럽 코테 스터디 1일차 TIL (미들러): [백준][Java] 1072 게임 - 실버3

 

문제 보기

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

 

 

풀이

1. 최소 몇 판 더 해야 하는지 구하기

최소 몇 판 이라는 말을 보고 바로 어떻게 풀어야 하는지 유추해 낼 수 있었다.

딱 5일 전 풀었던 문제와 비슷했기 때문이다.

이 문제는 이분 탐색 Lower bound로 풀 수 있다.

 

같은 백준의 실버3 문제인 IF문 좀 대신 써줘 포스팅을 참고하면 좋을 것 같다.

https://mountain-noroo.tistory.com/205

[백준][Java] 19637 IF문 좀 대신 써줘 - 실버3

 

int goal = (int)(y * 100 / x);
// -1 예외 처리
goal++;

int low = 0;
int high = (int)x;
while (low <= high) {
  int mid = (low + high) / 2;
  int winning = (int)((y + mid) * 100 / (x + mid));
  if(winning >= goal) {
    high = mid - 1;
  } else {
    low = mid + 1;
  }
}

 

백분율 구하는 법
일부 * 100 / 전체

 

현재 백분율에 1을 더한 값을 목표 지점으로 선택하고

mid 판 만큼 더 이겼을 때의 백분율을 계산해서

목표보다 크거나 같으면 high를 줄이고 작으면 low를 높인다.

 

백분율 구하는 법에 좀 이슈가 있었는데

y * 100 / x가 아니라 y / x * 100으로 계산할 경우 나눗셈으로 발생하는 부동 소수점 오차가 *100으로 인해 증폭 될 수 있다.

이 점을 주의하면 오차 문제는 해결 될 것이다.

 

 

2. -1 예외 처리는 어떻게?

 

문제 해결은 쉬운데 개인적으로 -1 예외처리를 하는 과정에서 애를 먹었다.

Z가 절대 변하지 않는 경우가 처음 부터 100%인 경우 밖에 없다고 생각했었기 때문!

하지만 이는 잘못 된 생각이다.

99%인 경우에 아무리 승을 더해도 99.99999.....가 될 뿐 절대 100이 될 수 없기 때문이다!!

 

int goal = (int)(y * 100 / x);
if(goal >= 99) {
  bw.write(-1 + "");
  bw.flush();
  bw.close();
  return;
}

goal++;

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String[] inputs = br.readLine().split(" ");
    double x = Integer.parseInt(inputs[0]);
    double y = Integer.parseInt(inputs[1]);

    int goal = (int)(y * 100 / x);
    if(goal >= 99) {
      bw.write(-1 + "");
      bw.flush();
      bw.close();
      return;
    }

    goal++;

    int low = 0;
    int high = (int)x;
    while (low <= high) {
      int mid = (low + high) / 2;
      int winning = (int)((y + mid) * 100 / (x + mid));
      if(winning >= goal) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }

    bw.write(low + "");

    bw.flush();
    bw.close();

  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/1072.%E2%80%85%EA%B2%8C%EC%9E%84

CodingTest_AutoSave/백준/Silver/1072. 게임 at main · MetroDefro/CodingTest_AutoSave