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

🔗문제 보러가기

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

 

 

문제 설명

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

 

---

입력

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

 

---

출력

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

 

---

예제 입출력

 

---

풀이 전략

반복문을 통해 날짜를 하루하루 카운트해가며 계산해볼 순 있겠지만, 그러면 예제 3번에서 바로 시간 초과가 날 것 같다는 생각이 바로 들었습니다. 수학적인 방정식을 세워서 구해야겠더군요.

제가 생각했던 방법은 이랬습니다. 어차피 밤엔 미끄러져 내려가기에, n번째 날에 낮 동안 올라간 높이만 보면 되겠다구요. n번째 낮 동안 달팽이가 올라간 높이는 다음과 같습니다.

(n * 낮에 올라가는 A미터) - (n - 1) * 밤에 미끄러지는 B미터

 

위 식을 토대로, 우리는 다음과 같은 부등식을 세울 수 있습니다.

정상높이 <= (n * 낮에 올라가는 A미터) - (n - 1) * 밤에 미끄러지는 B미터

 

코드로 변환하면 다음과 같겠지요.

// 정상높이 : topHeight
// n번재 날 : days
// 낮에 올라가는 높이 : climbingHeight
// 밤에 미끄러져 내려오는 높이 : slipHeight

topHeight <= days * climbingHeight - (days - 1) * slipHeight;

 

우리의 목적은 days를 구하는 것이기에, 위 식을 days를 기준으로 정리해주면 됩니다.

1) topHeight <= days * climbingHeight - days * slipHeight + slipHeight;
2) topHeight - slipHeight <= days * (climbingHeight - slipHeight);

 

따라서, 다음 식으로 정리할 수 있습니다.

(topHeight - slipHeight) / (climbingHeight - slipHeight) <= days;

 

위 식에 대입하여 나온 days 값을 소수점 첫째자리에서 올림 처리를 해주면 정답을 구할 수 있습니다.

 

---

소스 코드 및 결과

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	unsigned int topHeight;          // 정상 높이(V미터)
	unsigned int climbingHeight;     // 낮에 올라가는 A미터
	unsigned int slipHeight;         // 밤에 미끄러지는 B미터

	cin >> climbingHeight >> slipHeight >> topHeight;

	unsigned int days = 1;
    
    // 소수점도 계산하기 위해 한 쪽을 실수형으로
	double result = static_cast<double>((topHeight - slipHeight)) / (climbingHeight - slipHeight);
	days = static_cast<unsigned int>(ceil(result));

	cout << days;
	return 0;
}