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

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

---

🖍 A미터 올라가고, B미터 미끄러지는 달팽이가 V미터의 나무 막대를 올라가는데 며칠이 걸리는지 구하는 문제
(link) 2869 달팽이는 올라가고 싶다

---

[풀이 과정]

시간 제한이 0.15초인 문제이다.
한마디로 노가다로 구하는 알고리즘은 소용 없고, 공식을 구해서 풀라는 의미

처음에 반복문으로 A올리고 B내리고 해서 구했다가 시간 초과 당했다.
그리고 이 문제는 제대로된 식을 구해도 시간 초과가 뜨는데, 언어를 java 11이 아니라 java 8로 설정해야 풀린다.

 

 

아무튼 공식 먼저 이야기 하자면 (V-A)/(A-B)+1 이라고 쓸 수 있다.

우선 총 거리인 V에서 올라갈 수 있는 거리 A를 빼준다.

(마지막 날에 A만큼 한 번 올라간다면 무조건 도착할 수 있는 거리를 만들어준 것이다. 따라서 그 후 연산에 +1이 있는 것)

그리고 A를 한 번 빼준만큼의 지점에 도착하기 전까지는 하루에 도달하는 거리가 (A-B)m이기 때문에,

(V-A)m에서 (A-B)m를 나누어주면 (V-A)m까지 도달하는 데 며칠이 걸리는지 알 수 있다.

 

그런데 이때 예외의 경우가 하나 있기 때문에 조건문으로 경우의 수를 나누어줘야한다.
바로 (V-A)/(A-B) 연산을 했을 때 나머지가 나오는 경우이다.

우리가 지금 구하는 것은 거리이므로, 나머지가 나온 경우 몫만큼의 일 수를 쓰고도 남은 거리가 있다는 뜻이다.

따라서 나머지가 나온 경우에는 하루를 더 사용해야 한다. 그렇기 때문의 기존의 식에서 +1 더해주므로, 나머지가 나오는 경우의 공식은 (V-A)/(A-B)+2가 된다.

---

[Pseudocode]

1. 낮에 올라갈 수 있는 거리를 입력받을 변수 A
2. 밤에 미끄러지는 거리를 입력받을 변수 B
3. 나무 막대의 총 길이를 입력받을 변수 V
4. if((V-A) % (A-B) ==  0)
    5. (V-A)/(A-B)+1 출력
6. else
    7. (V-A)/(A-B)+2 출력

.. 보다시피 수학 문제이므로 의사 코드가 중요한 문제는 아닌 것 같다.

---

[Code]

import java.util.*;

/**
 * 백준 2869번
 * 달팽이는 올라가고 싶다
 * 분류: 수학
 */
public class Problem6 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int A = input.nextInt(); // 낮에 올라갈 수 있는 거리
        int B = input.nextInt(); // 밤에 미끄러지는 거리
        int V = input.nextInt(); // 나무 막대의 총 길이

        if((V-A) % (A-B) == 0)
            System.out.println((V-A)/(A-B)+1);

        // 나머지가 있을 경우, 남은 거리는 하루를 더 소비해야 하므로 +1
        else
            System.out.println((V-A)/(A-B)+2);

        input.close();
    }
}

---

[Result]

---

(2021.07.18)

인생을 찐 문과로 살다보니까 수리문제에 많이 약하다.

그래서 이 문제는 풀이를 참고했다.