[백준]2869. 달팽이는 올라가고 싶다

[문제]

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

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

[고려사항]

<시간초과> : 무작정 처음부터 반복문을 돌리면 시간초과가 뜸

<아침> : 아침에 goal을 넘으면 더이상 달팽이가 내려오지 않는 것을 고려해야 함

[풀이]

시간초과가 걸리지 않기 위해서, 달팽이의 시작점(start)을 goal과 최대한 가까운 숫자로 정해야 한다. 이때, 시작점은 a - b (하루동안 달팽이가 가는 거리)로 나누어 떨어져야 한다. sum은 지나간 날(day)이다.

1. 대략 start의 위치를 goal과 최대한 가깝게 하기 위해 goal - a의 값을 start로 잡는다.

2. start의 값보다 작으면서 a-b로 나누어 떨어지는 최댓값을 구한다.

3. 이때의 날짜를 sum에 넣는다.

4. while문을 통해 달팽이가 goal을 처음으로 넘는 날을 구한다.

5. goal을 넘지 못했다면 달팽이가 다시 떨어지는 것까지 구현해준다.

6. goal을 넘었다면 그것은 아침이기 때문에 sum(날짜)를 하나 더 더해주고 break로 빠져나온다.

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
	long long a, b, goal, sum = 0, start = 0;

	scanf("%llu %llu %llu", &a, &b, &goal);

	start = goal - a;
	while (start%(a-b)!=0) {
		start--;
	}
	sum = start / (a - b);

	while (start < goal) 
	{
		start += a;
		if (start >= goal) {
			sum++; //다음날이당
			break;
		}
		start -= b;
		sum++; //하루가 지났당
	}
	printf("%lld", sum);

	return 0;
}

#노력의 산물