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

링크

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

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

풀이

시간 제한이 0.15초로 짧기 때문에 반복문을 이용하면 시간 초과가 뜹니다.

그렇기 때문에 식으로 계산해주면 편합니다.

 

달팽이가 정상에 도착하면 더 이상 미끄러지지 않습니다.

바로 이 부분에서 문제해결의 실마리를 찾을 수 있습니다.

 

우리의 목적지는 더 이상 V가 아니라 V-A가 됩니다.

V-A 또는 V-A < X < V에 달팽이가 위치한 상태에서 cnt+1만 해주면 되기 때문입니다.

 

그러면 다시, 달팽이는 V-A 또는 V-A < X < V로 와야합니다. 달팽이는 하루에 A-B만큼 움직이기 때문에

(V-A) / (A-B)라는 식을 통해서 며칠이 지나면 저 위치로 갈 수 있는지 구할 수 있습니다.

V-A의 위치로 딱 떨어지게 오는 경우는 상관 없지만, 그렇지 못 한다면 (V-A) / (A-B)는 나머지를 가지고 있을 것이고, 이는 하루가 더 지나야 합니다.

 

결론적으로 cnt는 세 가지에 의해 결정됩니다.

1. (V-A) / (A-B)

2. (V-A) % (A-B)

3. 하루 더

 

이는 코드로 구현하면 다음과 같습니다.

cnt = (v - a) / (a - b);
cnt += (v - a) % (a - b) ? 1 : 0;
cnt++;

 

코드

//2869_달팽이는 올라가고 싶다
#include <cstdio>
using namespace std;

int a, b, v, cnt;

int main() {
	scanf("%d %d %d", &a, &b, &v);

	cnt = (v - a) / (a - b);
	cnt += (v - a) % (a - b) ? 1 : 0;
	cnt++;

	printf("%d\n", cnt);

	return 0;
}