백준 2869

백준 2869번을 풀어보았다.

 

올라간 후에도 V보다 작다면 필연적으로 밤을 지내며 B만큼 미끄러지게 되므로 올라간 것을 기준으로 생각하였다.

 

즉 첫째 날에는 A만큼, 둘째 날에는 -B+A만큼, 셋째 날에도 -B+A만큼 올라간다.

 

시간 제한이 있는 문제로, 처음에는 단순한 반복문으로 풀었다가 시간 초과가 나왔다.

let [A, B, V] = require('fs').readFileSync('/dev/stdin').toString().split(' ').map(Number)

let day = 1, distance = A

while (true) {
  if (distance >= V) {
    break
  }

  day += 1
  distance = distance - B + A
}

console.log(day)

while (true) { if (distance >= V) 는 while (distance >= V)로 표현할 수 있다.

 

참고) 백준 2292번, 백준 1193번

그래서 반복이 필요 없는 수식으로 접근해야겠다는 생각이 들었고, 크게 두 가지 풀이가 있다.

 

1. Math.ceil((V-A)/(A-B)) + 1

 

예를 들어 2 1 5를 입력받은 경우 2 + (-1+2) *  3  ≥ 5 가 되어 4일이 걸리고 (3일에 첫째날 1일을 더해주었다)

 

이를 정리해보면 __ ≥ (V-A)/(A-B) + 1인 최소 정수가 답이 된다.

 

최소 정수라는 조건을 반영하여 식을 정리해보면 __ = Math.ceil((V-A)/(A-B)) + 1이다.

 

이를 코드로 작성해보면 다음과 같다.

let [A, B, V] = require('fs').readFileSync('/dev/stdin').toString().split(' ').map(Number)

let day = Math.ceil((V-A)/(A-B)) + 1

console.log(day)

 

2. Math.ceil((V-B)/(A-B))

 

위 풀이는 V-A로 첫째날에 올라간 높이를 미리 빼준 뒤 이를 이후 하루동안 실제로 올라갈 수 있는 높이 A-B로 나누었고,

 

때문에 첫째날을 포함하기 위해 1을 더해주었다.

 

그러나 V-B로 마지막 날에 미끄러질 높이를 빼 달팽이가 실질적으로 올라가면 되는 높이를 구한 뒤 이를 A-B로 나눠줄 수도 있다.

 

이 경우 1을 더해줄 필요가 없어진다.

let [A, B, V] = require('fs').readFileSync('/dev/stdin').toString().split(' ').map(Number)

let day = Math.ceil((V-B)/(A-B))

console.log(day)