[BOJ] 백준 2869번 : 달팽이는 올라가고 싶다 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/2869

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

문제

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

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

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

 

풀이

범위가 최대 1,000,000,000까지 주어지므로 반복문을 이용하면 필연적으로 시간 초과가 발생하기때문에 O(1)의 시간으로 문제를 푸는 것이 적합해 보입니다. 따라서 수학적 지식을 활용하여 수식을 만들어 내는 것이 관건이었습니다.

우선, 문제에서 주어진 A = 2, B = 1, V = 5를 예시로 들어 설명하겠습니다. A는 낮 사이 올라가는 길이고, B는 밤 사이 미끄러져 내려가는 길이이므로 아래와 같은 그림으로 표현할 수 있습니다.

여기서 중요한 것은 올라갔다 내려갔다를 반복하는 (A - B)를 마지막 목적지에 도달하고나서는 수행하면 안 된다는 점입니다. 따라서 미리 V - A를 함으로써 목적지에 도달하기 바로 전 단계에서 종료하기로 하였습니다.

아래 그림에서 동그라미친 부분이 V - A를 한 장소입니다.

이제 우리가 할 일은 하나 밖에 없습니다. 바로 올라갔다 내려갔다하면서 동그라미 친 곳에 도달하려면 몇 번 반복해야하는지를 구하면 됩니다. 그것은 (V - A) / (A - B)를 함으로써 도출해 낼 수 있습니다.

하지만, 이것은 아직 목적지에 도달한 것이 아니므로 (V - A) / (A - B)를 한 값에 1을 더 해주어야 정답이 됩니다.

단, (V - A) / (A - B)를 한 값을 올림 처리를 해 주어야 합니다. 만약 A = 3, B = 1, V = 6일 경우 V - A = 3, A - B = 2이므로 최종적으로 3 / 2 = 1.5가 됩니다. 날짜는 정수로 표현해야하고, 소수점으로 나올 시 이 값보다는 큰 정수로 나타내야하므로 올림 처리를 해야하는 것입니다.

따라서 최종적인 식은 ceil((V - A) / (A - B)) + 1이 되겠습니다.

소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int A = Integer.parseInt(st.nextToken()); // 낮 동안 올라가는 거리
        int B = Integer.parseInt(st.nextToken()); // 밤 동안 미끄러지는 거리
        int V = Integer.parseInt(st.nextToken()); // 도달해야하는 높이
        
        double x = (double) (V - A) / (A - B);
        
        int ans = (int) Math.ceil(x) + 1;
        
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.