[Algorithm/JS] 백준 2869번 달팽이는 올라가고 싶다

🔗 문제 바로가기 (opens new window)

Question

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

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

Input

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

Output

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

Example

Input 1

2 1 5

Output 1

4

Input 2

5 1 6

Output 2

2

이 외의 입출력은 상단의 문제 바로가기 링크에서 확인

Solution 1 (실패)

const [A, B, V] = require('fs')
  .readFileSync('../input.txt')
  .toString()
  .trim()
  .split(' ')
  .map(Number);
let day = 1; // (1)
let sum = 0; // (2)
while (true) {
  sum += A; // (3)
  if (sum >= V) {
    // (4)
    break;
  }
  sum -= B;
  5;
  day++;
}
console.log(day);

1. 정상에 도달하기까지의 일수, 기본 하루를 초기값으로 설정
2. 달팽이가 올라간 총 거리
3. 낮에 올라간 거리를 더해준다.
4. 밤이 오기 전, 낮에 정상(V)까지 도달할 수 있기 때문에 if 문을 미끄러진 거리(B)를 빼기 전에 작성해야한다. 정상(V)보다 올라간 총 거리가 크거나 같다면 반복문을 빠져나간다.
5. 다음으로 미끄러진 거리를 총 거리에서 빼준다.
6. 밤이 지나면 하루가 끝나기 때문에 day 를 증가시킨다.

이번 문제는 꽤 쉬워서 간단하게 풀었다고 생각했지만 결과는

시간초과

좀 더 계산 적으로 접근해 보기로 했다.

Solution 2 (성공)

/**
 * 올라가야하는 총 거리 = 정상까지의 거리 - 미끄러진 거리
 * 하루에 올라가는 거리 = 낮에 올라간 거리 - 밤에 미끄러진 거리
 * 총 거리 / 하루 = 소요 일
 *
 * 소요 일 = (V - B) / (A - B)
 */

const [A, B, V] = require('fs')
  .readFileSync('../input.txt')
  .toString()
  .trim()
  .split(' ')
  .map(Number);
console.log(Math.ceil((V - B) / (A - B)));

달팽이가 **올라가야하는 총 거리(총 거리)**와 **하루에 올라갈 수 있는 거리(하루 거리)**를 구해 총 거리에서 하루를 나누면 총 소요되는 일 수를 계산할 수 있을 것이다.

연산식으로 작성하면 이와 같다.

총 거리 = 정상까지의 거리 - 미끄러지는 거리
하루 거리 = 낮에 올라간 거리 - 밤에 미끄러진 거리

소요 일 = 소요 거리 / 하루 거리

소요 일 = (V - B) / (A - B)

결과는

통과!