[코딩테스트 23일차] BAEKJOON 2869번 : 달팽이는 올라가고 싶다

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

[문제]

---

[고찰]

저는 해당 문제에 대해서 문제 그대로 해석하고 코딩하여서 답변을 제출하였습니다.

무한 루프 속에서 달팽이의 현재 위치를 확인하면서 날짜를 1씩 더했습니다만, 시간 초과로 실패하였습니다.

 

그래서 답변을 찾아보니, 반복문을 사용할 경우 모조건 시간초과가 발생하는 문제였고,

해당 문제는 수학적으로 풀기만 하면 되는 간단한 문제였습니다.

 

아래는 제가 작성한 코드입니다.

#include <iostream>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int A, B, V;

	cin >> A >> B >> V;

	int current = 0;
	int day = 0;

	while (1)
	{
		day++;
		current += A;

		if (current >= V)
		{
			cout << day;
			return 0;
		}
		else
		{
			current -= B;
		}
	}

	return 0;
}

---

[개념]

해당 문제는 달팽이가 마지막 날에 미끄러지지 않는다는 점이 핵심 중점이며, 정상에 올라간 순간 바로 도착을 한다는 것을 생각하여야 합니다.

 

따라서 목표는 단순히 V가 아닌, 마지막 날 낮에 A만큼 올라가서 처음으로 V 이상이 되는 시점인 V - A가 목표가 됩니다.

 

목표를 V - A라고 생각했을 때, 달팽이는 V - A까지 A - B만큼 반복해 올라가며, 마지막 날에 A만큼 올라가서 끝이 납니다.

 

이를 수식으로 정리하면 (V - A) / (A - B) + 1이 됩니다. (여기서 1을 더해주는 이유는 마지막 날을 고려했기 때문입니다.)

 

 

주의할 점은 (V - A) / (A - B)가 나머지가 생길 수 있다는 점입니다.

나머지가 생겼을 때는 하루가 더 필요하다는 뜻이기 때문에 이에 대한 처리도 해줘야 합니다.

 

이에 대한 방법은 3가지가 있습니다.

 

[나머지에 대한 예외처리]

나머지에 대한 예외처리 방법은, 나머지가 존재할 때 day를 1 더해주기만 하면 됩니다.

int day = (V - A) / (A - B) + 1;
    
if ((V - A) & (A - B) != 0)
    day++;
   
cout << day;

 

[ceil() 함수 활용]

정수 나눗셈은 버림 방식이기 때문에, ceil() 함수를 사용하여 나머지가 존재할 경우 day를 자연스럽게 1을 더하게 됩니다.

#include <cmath>

// ...


int day = ceil((double)(V - A) / (A - B)) + 1;
cout << day;

 

[올림을 정수 나눗셈으로 처리]

올림 함수 아래의 공식이 적용됩니다.

ceil(X / Y) = (X + Y - 1) / Y

 

X / Y는 정수 나눗셈이기 때문에 소수점 이하는 버려집니다. 이때 X에 Y - 1을 더한다고 해도, Y보다 작은 값을 더하는 것이므로
몫이 두 단계 이상 증가하지는 않습니다.

그러나 나머지가 존재하는 경우에는, Y - 1을 더함으로써 몫이 정확히 한 단계 올라가며, 의도한 올림(ceil) 효과를 정수 연산으로 얻을 수 있게 됩니다.

즉, Y - 1은 나머지가 있을 때만 반응하는 안전한 조정 값입니다.

int day = (V - B - 1) / (A - B) + 1;
cout << day;

---

[정리]

예전에도 비슷한 실수를 했던 것 같지만, 전체적인 흐름을 쫒다 중요한 포인트를 놓친 것 같습니다.

문제량을 더욱 늘려 많은 경험을 해야할 것 같습니다.

---

[Solution - 올림을 정수 나눗셈으로 처리]

#include <iostream>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int A, B, V;

	cin >> A >> B >> V;

	int day = (V - B - 1) / (A - B) + 1;
	cout << day;

	return 0;
}