[BOJ/C++] 달팽이는 올라가고 싶다(2869번)

1. 문제 개요

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

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

1-1. 설명

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

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

1-2. 제한 사항 

 - 첫째 줄에 A, B, V가 공백으로 구분되어서 주어짐

 - 1 <= B < A <= V <= 1,000,000,000

---

2. 구현

2-1. 풀이

시간 제한이 0.15초이므로, 반복문을 통해 일일히 계산하면 당연히 시간 초과가 발생한다. 수학적인 접근을 통해 수식을 만들어야 한다. 달팽이의 하루 이동거리는 A-B가 되고, 마지막날에는 A-B가 될 수 있고, A가 될 수 있다.

이를 신경써서 수식을 정리해보자. 달팽이의 이동 횟수는 N으로 정의한다. 정리하면 N >= (V-B) / (A-B)가 나오게 된다. 만약 (V-B) / (A-B)가 나머지없이 떨어지게 된다면 이것이 답이되며, 나머지가 존재하면 올림처리를 진행해야 한다. 수식을 찾지 못해 질문 게시판을 참고하여 코드를 작성하였다.

2-2. 코드

#include <iostream>
#include <cmath>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int A, B, V;

	cin >> A >> B >> V;
	int day = ceil((double) (V - B) / (A - B));
	cout << day << "\n";
}