[BOJ] 백준 2869 달팽이는 올라가고 싶다-java

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

문제:https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

 <수학> 버전

 <이분탐색> 버전

 

 

풀이

이번 문제는 사실 문제 설명이 3줄이라 쉬울 것이라고 생각했다. 하지만.. 정답률 28% ^^! 시간 제한이 0.15이다. 하지만 이분탐색 문제를 풀어보고싶어서 골랐다.

이분탐색으로 접근하려 했지만 .. 보자마자 <수학>버전으로 접근해버렸다. 수학으로 풀면 너무 쉬운데 도대체 어느 부분을 이분탐색으로 접근해야 한다는거죠? 이미 통과해버렸는데 ,,, 🤔

그렇지만 이분탐색으로 푸는 것이 목적이였기에 이분탐색으로 접근해보았다. 

<수학> 버전

수학 버전은 아주 간단하다. 마지막만 미끄러지지않기 때문에 하루에 가는 양은 (아침에 올라가는 A) - (밤에 미끄러지는 B) 이다. 그런데 마지막에는 A만 더해야 하므로 마지막 A를 전체 V에서 뺀다. 그럼 V-A가 된다. 여기서 A-B로 나누면 결국 마지막 날을 제외한 날들이 며칠 반복되어야 하는지 알 수 있다. 그치만 int형은 소수점을 버리기 때문에 A+(A-B)*n이 V를 넘는지 확인하고 넘으면 바로 answer출력, 넘지않으면 1을 더한다.

<이분탐색> 버전

이분탐색으로 어떻게 접근해야할지 많이 고민해봤다. 굳이 이분탐색으로 접근해야 한다면 이렇게 해보자.. 일단 며칠동안 올라오고 미끄러지고 그렇게 반복하다 마지막 날에 A만큼 올라갔을 때 V에 도달하는 순간을 알아내야 한다. 그러기위해서 나는 high = V로 두어서 이분탐색을 시도했다. 

방법은 이렇다. high와 low의 중간 값인 mid가 있다. 이 mid를 A-B로 나눈다. 그럼 n이 나오고 그 값을 일단 answer에 저장한다. 그 후 mid까지 왔다고 생각하고 V-mid를 A가 한번에 갈 수 있는지 확인한다. A만큼 갔을 때 V에 도달한다면 두 가지의 경우로 나뉜다.

1. A만큼 갔는데 V-A의 값이 A-B보다 작다면 정답이다. 
2. A만큼 갔는데 V-A의 값이 A-B와 같거나 크다면 answer는 더 작아질 수 있기에 정답이 아니고 다시 이분탐색을 한다.

위와 같이 나뉘는 이유는 A = 6000, B = 5000, V= 10000이라고 해보자. 이 경우 이분탐색을 처음 시도할 때, mid = 5000이다. 그럼 5000/(6000-5000) = 5이다. 그리고 V-mid = 5000이다. 이 상황에서 A만큼 가보자. 그럼 11000이 되는데 이때 사실 4일이 지나고 5일째 날에 5000을 갔으면 딱 10000이 되었을 것이다. 그 이유는 5000/(6000-5000) + 6000 >= A-B 이기 때문이다. 이렇다면 적어도 하루이상은 더 전에 도달했을 것이라는 뜻이다. 그렇기 때문에 이분탐색을 아래부분으로 다시한다.

이어서 얘기해보자면  V-mid를 A가 한번에 갈 수 있는지 확인했을 때, V에 도달하지 못한다면 며칠을 더 올라와야 마지막 날에 A만큼 올라갔을 때 도달할 수 있다. 그러므로 이분탐색을 윗부분으로 다시한다.