문제

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

입력

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

출력

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

접근방법

1. 입력 처리: 공백으로 구분되어 입력받는걸 한 줄 읽어 ' '을 구분자로 각 int변수에 넣어줄까 생각해봤지만 scanf를 사용하면 그럴 필요가 없었다. scanf("%d %d %d", &A, &B, &V) 로 효율적인 처리가 가능했다.2) 솔루션: 달팽이가 목적지에 도달하는 그 날은 밤이 찾아오지 않는다. 도달하는 날을 n이라고 가정하면 결국 V <= nA - (n-1)B 가 될 것이다. 여기서 n을 구하려면 nA - (n - 1)B 에 B를 하나 더 빼준뒤 A-B를 나눠주면 n을 구할 수 있을 것이다. A-B를 나눈 결과가 나눠 떨어지지 않을 경우 n은 +1을 해줘야 할것이다. 그런 경우를 특정하기엔 코드의 효율이 떨어지므로 L - B 를 할 때 -1을 해주고 결과에 +1을 해줌으로 정확한 날짜를 구할 수 있게 된다.즉, days = (V - B - 1) / (A - B) + 1

깨달은 점

처음엔 반복문을 사용해서 접근했다. 그런데 시간초과 문제가 발생했다. 결국 시간을 줄이기 위해 다른방법을 생각해야 했고, 위 방법이 그 해결책이다. 더하고 빼기를 반복하는 시간을 수학적인 접근방법을 통해 더 효율적으로 해결할수 있다는걸 깨달았다.

#include <stdio.h>

int main(void)
{
int A, B, V;
int days;

scanf("%d %d %d", &A, &B, &V);
days = (V - B - 1) / (A - B) + 1;
printf("%d", days);
return (0);

}