백준 / 수학 / 2869번 / 달팽이는 올라가고 싶다 / C++

문제

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

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

 

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

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

 

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int days;
	int a, b, v;
	cin >> a >> b >> v;
	
	days = (v-b-1)/(a-b)+1;
	
	cout << days << '\n';
	
	return 0;
}

---

처음 풀때 쉽게 생각해서 반복문으로 푸려는 사람이 많을것이다. (나도그랬다)

그러면 시간초과가 나므로 결국 다른방법으로 풀어야 한다.

 

우선 문제를 수식으로 간단히 나타내보자.

하루에 A만큼 올라가고 B만큼 떨어지므로 결국 하루에 올라가는 높이는 A-B이다.

그리고 올라가야하는 총높이는 마지막날에 도착하면 떨어지지 않으므로 V-B이다.

 

그럼 결국 (V-B)/(A-B)로 간단히 일수를 구할 수 있다.

하지만 정확히 나누어 떨어지지 않을경우 계산에 문제가 생긴다.

 

예를들어 나누었을때 2.25가 나왔다고 치자.

그럼 0.25만큼 하루 더 올라가야 한다. (소수점이 생길경우 올림연산)

위의 계산식대로 하면 3과 2.25는 int형으로 계산하기 때문에 다른 숫자가 된다. (3과 2)

 

분자가 9일때 분모가 3인경우와 4인경우가 있다고 하자.

결국 소수점이 생기면 올림연산을 해야한다.

cmath의 ceil을 사용해서 보기좋게 풀 수도 있다.

 

결국 3과 2.xxx...는 동일하게 3의 값을 가져야 하기때문에 ceil연산을 사용하는 방법이 첫번째이고,

분자에서 먼저 1을빼고 시작하면 위의 예시로는 2.xxx와 2를 가져서 동일한 정수값을 가진다.

따라서 원래 구하려는 값인 3을구하기 위해선 마지막에 +1만 해주면된다.

 

그래서 결국 수식은 (v-b-1)/(a-b)+1이 되는것이다.