[백준2869_자바스크립트(javascript)] - 달팽이는 올라가고 싶다

🔴 문제

달팽이는 올라가고 싶다

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [a, b, v] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split(' ')
  .map(Number);

console.log(Math.ceil((v - b) / (a - b)));

🟢 풀이

⏰ 소요한 시간 : 10분

처음에는 아래와 같은 코드르르 짰는데 자세히 보니 이 문제의 시간복잡도가 0.25초...n의 범위가 1,000,000,000이라 아래 코드로 돌리면 최소 10초의 시간이 필요하다.

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [a, b, v] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split(' ')
  .map(Number);

let goal = 0;
let day = 0;

while (goal < v) {
  goal += a;
  day += 1;

  if (goal >= v) break;

  goal -= b;
}

console.log(day);

그래서 공식을 세워줬다.

우리가 찾고자 하는 ans를 식으로 표현하면 다음과 같다.

ans * (a - b) + b >= v 
ans >= (v - b) / (a - b)

따라서 (v - b) / (a - b) 이 공식을 올림 처리 해주면 정답

🔵 Ref