[C] 백준 2869번 - 달팽이는 올라가고 싶다

 문제를 읽고, "반복문으로 V(높이)가 될 때까지 반복하면 되겠구나"라고 생각해서 아래의 코드를 작성했고, 결과는 시간 초과가 나왔다. 알고 보니 수학 문제였고, "예시를 통해 공식을 찾는 것이구나"하고 깨달았다.

#include <stdio.h>

int main()
{
	int height = 0;
	int day = 0;
	int A, B, V;

	scanf_s("%d %d %d", &A, &B, &V);
	while ((height += A) != V)
	{
		height -= B;
		day++;
	}
	printf("%d", day+1);
}

 

 예시

① A=2, B=1, V=5 → X=4

1) 0+2-1=1

2) 1+2-1=2

3) 2+2-1=3

4) 3+2

 

② A=3, B=1, V=5 → X=2

1) 0+3-1=2

2) 2+3

 

 두 가지 예시를 보고 아래의 공식을 찾았다.

→ AX-B(X-1)=V

→ AX-BX=V-B

→ X=(V-B)/(A-B)

그런데, 정답이 아닌 것이다. 도저히 모르겠어서 구글링 해봤더니 공식이 나눠떨어지는 경우, 나눠떨어지지 않는 경우를 생각해야되는 것이었다.

 

※ 여기서는 x=V-B, y=A-B라 가정

1) 나눠떨어지는 경우

   x/y=d (d는 임의의 정수) ex) 6/3=2

   그런데 int형은 소수점을 잘라내므로,

   (x-1)/y=d-1(나눠떨어지지 않는 경우)에 +1을 하면 원래(나눠떨어지는 경우)의 d가 된다.

   d=(x-1)/y+1 ex) 5/3+1=2

   이를 아래의 경우로 증명한다.

 

2) 나눠떨어지지 않는 경우

   x/y=d+f (d는 임의의 정수, f는 0<f<1을 만족하는 실수)

   x=y(d+f)

   x-1=y(d+f)-1

   (x-1)/y=d+f-1/y → 1/y는 소수점이 되니까 int형에서는 잘린다.

   그러므로 (x-1)/y=d+f-1/y=d+f이 되고,

   여기에 +1을 해주면 (x-1)/y+1(나눠떨어지지않는 경우+1)이 된다.

 

→ 따라서 (x-1)/y+1은 나눠떨어지는 경우와 나눠떨어지지 않는 경우 모두를 만족하는 식이 된다.

→ x,y를 원래 식으로 치환하면 (V-B-1)/(A-B)+1

#include <stdio.h>

int main()
{
	int A, B, V;
	scanf("%d %d %d", &A, &B, &V);
	printf("%d", (V - B - 1) / (A - B) + 1);
}

잘못된 점이 있으면 아래 댓글로 많이 남겨주세요!

감사합니다.