1072번 - 게임
감사합니다. 해결되었습니다.
제가 고려를 못했던 점은
1. x,y를 int로 선언한다면 z를 계산하는 과정에서 100*y를 해야하는데 이 때 y가 20억이라고 가정하면 오버플로우가 일어날 수 있습니다.
2. low, high, mid를 int로 선언한다면 (high는 Int 최대) high=(low+high)/2 계산에서 오버플로우가 일어날 수 있습니다.
즉 모든 변수가 int 범위에 속하더라도, 계산 과정에서 오버플로우가 일어날 수 있으므로 자료형을 long으로 해주어야 오버플로우로부터 안전합니다.
그리고 low = Long.MAX_VALUE인 경우에 대해서 문제점을 지적해주셨는데 그 경우는 find(mid)<=z인 경우가 계속되어 low=high가 되어 while문이 끝나게 되는 경우입니다.
그 경우는 99% -> 100%인 경우 또는 추가적으로 해야 하는 게임 수가 int의 최대 범위를 넘어서는 경우밖에 없습니다.
후자의 경우를 제외한다고 하면, 위의 z>=99 조건문에서 -1을 출력하게 됩니다.
댓글을 작성하려면 로그인해야 합니다.
oklshop 2년 전 0
어디가 문제일까요? 답도 잘나오고, x y는 문제에서 분명 10억 이하(int 범위 내)로 명시되어 있습니다.
이후 x,y를 나눌 때 소수점 계산을 위해 double로 선언했으며 문제에서 x,y는 int 범위 안에서만 존재하므로
Integer.parseInt로 읽어와도 무방합니다. (1000000000이면 x에는 1000000000.0 이런식으로 들어가겠죠)
그리고 y/x*100을 하고 int로 강제 형변환 하여 소수점을 잘라낸 값을 z에 저장했구요
게임을 얼마나 더 해야 하는 지에 대한 값들은 혹시몰라전부 long으로 처리했습니다.
이분 탐색에서 high도 Long.MAX_VALUE로 처리했구요
이 문제는 z가 z보다 커질 때의 lower bound를 구하는 이분 탐색 문제라고 나름대로 해석하여 풀었습니다.
(지금 다시 생각해보니 중복이 없어서 기본 이분탐색으로 풀어도 되겠네요)
아무튼 뭐가 문제인지 전혀 모르겠습니다 도움이 필요합니다