[C++] 백준 2869

백준의 2869번 달팽이는 올라가고싶다 문제이다.

 

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

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

---

 < 문제 >

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

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

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

 

 < 예제 >

 

문제를 정리하자면 이렇다.

달팽이가 낮에는 A만큼 올라가고 밤에는 B만큼 내려온다

V길이의 나무막대를 전부 올라가기 위해 걸리는 기간을 구하는 문제이다.

 

처음에는 이렇게 작성했었다.

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

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

	int A = 0, B = 0, V = 0;	 // A = 낮에 올라가는 높이, B = 밤에 떨어지는 높이, V = 막대의 길이
	cin >> A >> B >> V;

	int day = 0, length = 0;
	while (true) {
		length += A;
		day++;
		if (length >= V)
			break;
		else
			length -= B;
	}
	cout << day;
}

간단히 while문을 활용해서 작성을 했는데 이렇게 하면 시간초과가 된다.

그래서 while문을 활용하지 않은 다른 풀이법으로 문제를 풀어야했다.

 

 

그렇게 푼 코드는 다음과 같다.

먼저 a, b, v를 입력받고

	int day = 0;
	if ((v - a) % (a - b) == 0)
		day = (v - a) / (a - b);
	else
		day = ((v - a) / (a - b)) + 1;

정상에 도달하면 그 후로는 B만큼 내려오지 않기 때문에 낮에 A만큼의 길이를 올라갔을 때 정상일 경우에는 그때를 날짜로 정하였다.

그 외는 낮에 다 올라갔는데 A보다 조금 모자라게 남았을 경우에는 다음날 올라갈 수 있기 때문에 1을 더해주었다.

 

전체 코드는 이렇다.

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

int main() {

	int a, b, v;
	cin >> a >> b >> v;

	int day = 0;
	if ((v - a) % (a - b) == 0)
		day = (v - a) / (a - b);
	else
		day = ((v - a) / (a - b)) + 1;

	cout << day + 1;
}

 

시간초과를 처음 겪어봐서 좀 귀찮긴 했지만 정상에 도달했을 때는 미끄러지지 않는다는 점을 놓치지 않고 

원하는 식을 얻는다면 엄청 어려운 문제는 아니라고 생각한다.