오늘의 문제는 “2869번 달팽이는 올라가고 싶다”.
프로그래밍 문제뿐만이 아니라 논리 퀴즈로도 자주 보이는 문제이다.
보통은 달팽이가 구덩이나 우물에서 탈출하는 스토리지만 이 문제에서는 달팽이가 나무를 타고 올라간다고 한다.
달팽이가 낮에는 A미터만큼 올라가지만, 밤에는 자면서 B미터만큼 미끄러지는데, V미터를 올라가려면 몇일이 걸리는지 계산하는 문제이다.
보통 이 문제의 함정은 마지막 날에 A미터만큼 올라가서 V미터, 혹은 그 이상에 도달하면 그 날은 B만큼 미끄러지지 않는다는 점이다.
이 문제를 처음 본 순간 단순 반복문을 활용해서 코드를 짰었다.
#include <iostream>
using namespace std;
int main()
{
int a, b, v;
int day = 0;
int p = 0; //현재 위치
cin >> a >> b >> v;
while (p < v) //현재 위치가 v이하인 경우 반복
{
day++;
p += a; //낮에는 a만큼 올라가고,
if (v <= p) //v에 도달하면 반복문을 break
{
break;
}
p -= b; //v에 도달하지 못하면 b만큼 미끄러진다.
}
cout << day << "\n";
return 0;
}하지만 이 문제의 시간 제한은 0.15초로 매우 짧았고, 결국 시간초과가 났다.
0.15초를 극복하기 위해서는 단순반복이 아니라 수학 연산을 통해 바로 답을 구해야한다고 생각했다.
만약 D일이 걸려서 V에 도달한다면 다음 등식이 성립할 것이다.
AD - B(D - 1) = V
이 등식을 D에 대해 정리하면 다음과 같다.
D = (V - B) / (A - B)
#include <iostream>
using namespace std;
int main ()
{
int a, b, v, ans;
cin >> a >> b >> v;
ans = v - b;
ans /= (a - b);
cout << ans << "\n";
return 0;
}이 코드 역시 틀린 코드였다.
혹시 왜 틀린건지 못 찾은 분들은 여기서 잠시 멈추고 한 번 생각해보길 바란다.
생각보다 간단한 오류가 있다.