[백준 알고리즘] 문제 2869번 : 달팽이는 올라가고 싶다(JAVA)

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

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

---

1. 수식을 생각해보자.

1️⃣ A :  낮에 달팽이가 올라갈 수 있는 길이

2️⃣ B : 밤에 달팽이가 미끌어지는 길이

3️⃣ V : 달팽이가 올라갈 막대기의 길이

4️⃣ X : 올라가는 데에 걸리는 기간(날짜)

// 1일차 낮
V = A

// 2일차 낮
V = A - B + A

// 3일차 낮
V = A - B + A - B + A

// 4일차 낮 
V = A - B + A - B + A - B + A

낮으로 기준을 잡은 이유는 낮에 마지막으로 올라가면 그 길이에 도달하기 때문이다. 

위의 식을 살펴보면 하나로 묶을 수 있는 부분들이 나타난다.

V = (A-B)(X-1) + A

위의 식이 이해가 가지 않는다면, X에 기간을 대입해보면 이해할 수 있다. (첫날은 내려가지 않음!)

따라서 이 식을 바탕으로 문제에서 구해야하는 기간인 X를 구하는 식을 도출해보았다.

V = (A-B)(X-1) + A
V = AX - A - BX - B + A
V = AX - BX + B
V = X(A-B) + B

X(A-B) = V - B
X = (V-B) / (A-B)

---

2. 입력을 받고 수식을 대입해보자

import java.util.*;
import java.io.*;

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();

        long X = (long) Math.floor((V-B)/(A-B)); // ☝🏻
        // long X = (long)Math.ceil(((double)(V-B)/(double)(A-B))); // ✌🏻

        if((V-B) % (A-B) != 0){X++;}

        System.out.println(X);
    }
}

☝🏻Math.floor() 메서드로 내림을 해준 후, 나누었을 때 나머지가 있으면 X에 1을 더해준다.

✌🏻Math.ceil() 메서드를 사용할 경우, 아래의 if문은 필요가 없다.

    (+ 괄호 주의 할 것 !!! >> 실제로 괄호 주의 못해서 틀렸다.)

---

❗️ Scanner로 입력을 받았더니 시간초과 발생( + 타입이 long이어도 시간초과) ❗️

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int A = sc.nextInt(); // 낮에 달팽이가 올라갈 수 있는 길이
        int B = sc.nextInt(); // 밤에 달팽이가 미끄러지는 길이
        int V = sc.nextInt(); // 달팽이가 올라갈 막대기의 길이
        
        sc.close();
        
        int X = (int) Math.floor((V-B)/(A-B)); // 올라간 날
        
        if((V-B) % (A-B) != 0){X++;}
        
        System.out.println(X);
    }
}

처음에는 Scanner로 입력을 받았으나, 시간초과가 발생하였다. 당연한 소리이지만 타입이 어떠하든 시간초과가 발생함.