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

Link

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

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력 > 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
출력 > 첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

| 예제 입력

2 1 5

| 예제 출력

4

 

제출

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `100 99 1000000000`
)
  .trim()
  .split(" ");

const [A, B, V] = input;

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

console.log(day);

 

풀이과정

해당 문제는 시간 제한을 두고 있으므로 반복문을 사용해서 올라가고 내려가는 횟수를 count 하는 식으로 풀게 된다면, 시간 초과가 나올 것이다.

 

따라서 나무 막대의 높이까지 올라갈 때, (A-B)가 몇 번 반복되는지 찾으면 된다.

문제를 접근하는 방식은 다음과 같다.

 

(1) 문제에서 주어진 1 ≤ B < A ≤ V 조건에 의해 정상까지 오르기 위한 시간은 무조건 하루 이상이 걸린다.

(2) 정상까지 오르기 위해 걸리는 시간은 (A-B)가 반복된 횟수 + 1이다.

• A-B가 N번 반복되고, A만큼 올라갔을 때의 높이가 V보다 크거나 같으면 정상에 도달하기 때문이다.
  • if ) A = 2, B = 1, V = 5일 떄
  • day 1 : +2m  -1m  => 1m
  • day 2 : +2m  -1m => 2m
  • day 3 : +2m - 1m => 3m 
  • day 4 : +2m => 5m 정상 도달
  • 정상까지 걸린 일 수 = (A-B) * 3 + 1

이제 반복 횟수를 구해보자.

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

{(A-B) * repeat} + A = V 의 식을 정리하면, repeat = (V-A) / (A-B)이고, (1)번에서 봤듯이 repeat은 무조건 1 이상의 자연수이므로, Math.ceil() 메서드를 통해 나눈 숫자를 올림해준다.

 

(2)번을 통해, 반복 횟수에 + 1 한 값인 day를 출력하면 된다.

 

다른 풀이 )

다른 분들의 풀이와 비교해보니 좀 더 간단하게 생각해볼 수 있던 문제 같다.

(A-B) * day 가 V보다 크거나 같을 때 정상에 도달한다고 생각하면, day는 V / (A-B)의 식이 성립된다.

하지만, 정상에 올라간 후에는 미끄러지지 않는 조건에 의해서 위의 식처럼 day를 구하게 되면

불필요한 B가 추가로 더해지게 된다.

let day = (V-B) / (A-B)

따라서, V에서 B를 뺴준 값을 A-B로 나눠주어야 한다.

 

개념

Math.ceil()

• 주어진 숫자보다 크거나 같은 정수 중, 가장 작은 값을 리턴한다.
• 쉽게 말해, 올림해주는 함수이다.

 

---

Comment

백준 수학문제 1 단계에서 가장 적은 고민의 시간을 거쳤던 문제!

성장하고 있는 것 같아 굉장히 뿌듯함이 느껴졌다.