BOJ) 달팽이는 올라가고 싶다

달팽이는 올라가고 싶다

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

풀이

 

달팽이가 막대의 높이 V까지 올라가는 데, 걸리는 날을 구하는 문제다.

A는 달팽이가 낮에 올라갈 수 있는 높이이고, 

B는 밤에 잠을 자는 동안 아래로 미끄러지는 높이다.

정상에 올라간 후에는 미끄러지지 않는다.

 

위의 조건으로 미루어 봤을 때, 막대까지 오르는 날 * A 만큼 위로 올라가고, (막대까지 오르는 날 -1) * B 만큼 아래로 미끄러진다.

잠을 자는 동안만 미끄러지고, 높이까지 올랐을 때는 미끄러지지 않기 때문에, 막대까지 오르는날 -1 이라는 수가 나온다.

 

달팽이가 V까지 오르는 날은 최소 1일 부터, V일 까지 걸린다.

왜냐하면, A-B의 최소값이 1이기 때문에, V 높이까지는 V 일이 걸리기 때문이다.

 

위의 정보로, left =1, right =v를 초기값으로 넣어주고

mid를 통해 탐색을 한다.

mid 날 안에 오를 수 있으면, right = mid -1을 통해 걸리는 날의 최대 범위를 줄여주고,  answer에 mid를 저장한다.

반대로, mid 날 안에 오를 수 없다면, left =  mid +1를 통해 걸리는 날의 최소 범위를 높여준다.

 

답을 비교적 쉽게 구할 수 있다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long v = Long.parseLong(st.nextToken());
        br.close();

        solution(a,b,v);
    }

    private static void solution(long a, long b, long v) {
        long answer =0;
        long left =1, right = v;

        while(left <= right) {
            long mid = (left+right)/2;
            if(canClimb(a, b, v, mid)) {
                right = mid-1;
                answer = mid;
            } else {
                left = mid+1;
            }
        }
        System.out.println(answer);
    }

    private static boolean canClimb(long a, long b, long v, long days) {
        long height = a*days - b*(days-1);
        return height >=v;
    }
}