C언어 백준 2869번 달팽이는 올라가고 싶다. 풀이

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

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

 

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

 

 

풀이

 

시간초과 코드

#include <stdio.h>

int main() {
	int A, B, V;
	int x = 1;
	scanf("%d %d %d", &A, &B, &V);
	
	while (1)
	{
		if (A == V)
		{
			printf("1");
			break;
		}
		if ((A - B) * x + A >= V)
		{
			printf("%d", x + 1);
			break;
		}
		x++;
	}
	return 0;
}

while문을 돌리면 마지막 예제일 때 1,000,000,000번을 돌기 때문에 느리다. 

 

정답코드

 

#include <stdio.h>
#include  <math.h>
int main() {
	int A, B, V;
	
	scanf("%d %d %d", &A, &B, &V);
	
	
if (A == V)
{
	printf("1");
	return 0;
}

else
{
	(V - A) / (A - B);
	int x = V - A;
	int y = A - B;
	int a = ceil((double)x / (double)y);
	printf("%d", a+1);
	
}

	return 0;
}

Q)(V - A)/(A-B) 는 도대체 뭔가?

 

이를 이해하기 전에 먼저 (A-B)* a + A >= V를 이해해야 한다.

예를 들어 2 1 5 일 때를 생각해보자.

 

 

날	위치
day1	1M
day2	2M
day3	3M
day4	5M

day3 에서 3M는 어떻게 나왔을까?

(2-1) + (2-1) + (2-1) 이렇게 올라갔다 내려갔다해서 나온 것이다.

이는 다시 쓰면 (2-1)*3 이다.

 

이제 day4를 주목해보자

day4 에서의 5M는 (2-1)*3 +2 라는 식에서 도출된 것이다.

(A-B) *a + A = V인 것이다.

단, 여기서 A를 간 하루를 추가로 더해줘야하므로

day4 = day(a+1) = day(3+1)이다.

 

그렇다면  (A-B) *a + A > V일때는 어떨까?

당연히 상관없다. 그 지점이상을 도달한 것은 day에 영향을 주지 않아

상관이없다.

 

Q)(V - A)/(A-B) 는 도대체 뭔가?

다시 한번 위의 질문을 보자 a = (V - A)/(A-B) 이다.

일반적인 int형에서 '/'연산자는 정수만 return한다

따라서 실수형 return 을 위해 (double)형 변환을 해주었다.

 

Q)ceil은 왜 사용한것인가?

 5 1 6일 때를 생각해보자. (double)x/(double)y = 0.25이다.

a는 날짜인데 0.25day는 없다. 그렇다면 내림을 해줘야할 까 올림을 해줘야할까?

(A-B)* a + A >= V 우리는 이식을

간단히 표현한 것이다.

a = 0.25 일때 a는 0.25보다 큰 것이므로 ceil(올림)을 해준 것이다.