[Beakjoon Online Judge] 2869 - 달팽이는 올라가고 싶다(C++)

문제

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

입력

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

출력

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

 

어쩌면 초등학교 수학책 맨 뒤에 항상 있었던 "문제푸는 방법찾기"라는 단원에 있었을지도 모르는 문제겠다.

 

가장 처음 생각나는 건, 현재 높이를 나타내는 변수를 만들고, 이를 반복문 속에서 비교하며 올라갔다가 내려갔다를 구현하면 될 것 같다.

 

그러나 이 문제도 정답 비율 25%로, 어딘가 함정이 존재한다.

바로 시간제한 : 0.15초 (추가 시간 없음) 이다. 반복문으로 풀면 절대 안된다는 것이다.

만약 테스트 케이스 중 하루에 2미터 올라가고 1미터 떨어져서 1미터씩 올라가는데 10억미터를 올라가야한다는 경우가 있다면, 약 10억번의 연산을 해야하는데 이는 0.15초 안에 끝마칠 수 없다.

 

이러한 문제들은 식을 세워서 풀면 풀리는 경우가 있다.

만약 올라가야하는 날짜 수를 D라고 한다면,

D만큼 올라가고 떨어졌을 때 V와 같아야하므로

(A-B)*D = V일 때 D를 구하면 되겠다.

 

하지만 이 식에도 오류가 있다!

마지막 날에는 올라가서 다시 떨어질 이유가 없다. << 수학적으로는 이 부분이 문제의 키포인트다.

따라서 A*D - B*(D-1) = V일 때 D를 구해야한다.

 

A*D - B*(D-1) = V
A*D - B*D + B = V
(A-B)*D = V-B
D = (V-B) / (A-B)

(V-B)를 (A-B)로 나눈 것이 이 문제의 답이다.

 

그런데 여기서도 주의해야할 것이, 며칠이 걸리는지를 구해야하므로 D가 정수가 아닌 실수면 안된다.

float나 double로 선언하고 올림해도 되는데, 소숫점 밑으로 내림되는 int로 선언한 다음 조건문 하나를 써서 해결하겠다.

 

A*D - B*(D-1) < V일 때, D를 하나 올려주면 되겠다.

 

최종적인 코드는 다음과 같다.

 

#include <iostream>
using namespace std;
int main(void)
{
	int A, B, V, D;
	cin >> A >> B >> V;
	D = (V-B)/(A-B);
	if(A*D-(D-1)*B<V)
		D++;
	cout << D;
	return 0;
}

문제의 오답률이 무색할 정도로 짧은 코드가 나왔다.

 

코드의 시간복잡도를 낮추기 위해서는 수학적으로 푸는 것도 방법이 될 수 있겠다.

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 2869번 달팽이는 올라가고 싶다 C++

BOJ 2869번 달팽이는 올라가고 싶다 C++

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