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

 

---

 

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

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

또, 정상에 올라간 후에는 미끄러지지 않는다.

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

 

 

 

실행 결과

 

 

 

 

 

코드(c++)

#include <iostream>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long unsigned int a, b, v;
  cin >> a >> b >> v;
  cout << (v - b - 1) / (a - b) + 1;
  return 0;
}

 

 

 

 

코드 설명

 

문제가 짧길래 쉬운 줄 알았는데 생각보다 어려운 문제였다..

일단 문제에서 구하고자 하는 것은 달팽이가 올라가는데 총 며칠이 걸리는 지이다.

일수를 구하기 위해 문제를 마지막 날만 따로 분리해서 생각해야 한다!

이해하기 쉽게 최대한 풀어서 써보록 하겠다.

 

 

1. 달팽이가 정상에 도달하기 직전의 날까지 매일 a - b만큼 올라갈 것이다.

 

2. 달팽이가 정상에 도달하는 날, a만큼 올라가고 낮에 멈출 것이다.

    따라서 낮엔 올라가고 밤에 미끄러지는 경우의 수를 빼야한다. => (a - b)

 

3. (v - b) / (a - b)+1를 하면 되겠지..? 대충 일수가 나올 거라고 생각했다.

 

4.  만약 (v - b)가 (a - b)로 나누어 떨어지지 않을 경우, 3번 식을 적용할 수 없다.

     즉, 마지막 날에 달팽이가 조금이라도 더 올라야 할 때 마지막 날을 두번 고려하게 된다.

 

ex. 총 10미터 올라가야하고 3(a=5,b=2)미터씩 올라간다고 하자. 

마지막 날 제외하고 3*3=9미터를 올라간 후, 마지막날 1미터를 올라가서 총 4일이 걸린다.

3번 식을 적용하면 10-1/5-2=3, 따라서 3+1=4가 되므로 적용 가능하다.

하지만 이 식은 (v - b) / (a - b)가 나누어 떨어질 때만 통한다.

 

ex. 총 14미터 올라가야하고 3(a=5,b=2)미터씩 올라간다고 하자. 

마지막 날 제외하고 3*4=12미터를 올라간 후, 마지막날 2미터를 올라가서 총 5일이 걸린다.

3번 식을 적용하면 12-2/5-2=10/3=3.3333일이므로, 따라서 4+1이 되는 것이 아니라!!

int형을 입력받으몰 3.333이 내림되어서 3이 되어 하루를 덜 계산하게 된다.즉, 달팽이가 정상에 도달하기 직전의 날을 제대로 계산하지 못한다.

     

=> 달팽이가 정상에 도달하기 직전의 날까지의 일수 :  (v - b -1) 나누기 (a - b) 

 

5. 마지막으로 정상에 도달하는 날까지 1일을 더해줘야 총 일수가 나온다.

(v - b - 1) / (a - b) + 1

 

 

---

 

문제 출처:

https://www.acmicpc.net/problem/2869