백준 (C언어)백준 2869번 달팽이 (시간복잡도 문제)

이전에 풀었던 문제중에 시간복잡도에 자꾸 걸렸던 문제가 있었는데 시간복잡도를 줄이는 방법은

1. 함수의 호출의 수를 최대한 줄인다.

2. 미리할 수 있는 연산은 미리 끝내고 반복문에 들어간다.

3. 이번에 풀 문제인데 탐색할 때 값을 계속 올리면서 찾는 것보다 수식으로 풀고 코드를 짜는게 낫다는 거다.

#include<stdio.h>

int main()
{
	unsigned int up, down;
	unsigned int high;
	scanf("%d%d%d", &up, &down, &high); 
	unsigned int  day = 1;
	unsigned int cha = up - down;
	unsigned int real_high = high - down;
	while (1)
	{
		if (real_high <= (cha*day))
		{
			printf("%d", day);
			return (0);
		}
		day++;
	}
}

내가 처음 짠 코드는 다음과 같다. 기것마자 시간을 줄여보겠다고 최대한 해봤지만 문제 조건에는 충족하지 못했다 그래서 다른 방법을 찾아 봤는데

우리가 구하고 싶은게 day니까 day를 쉽게 구하는 방법을 찾아봤다.

일단 조건식이 up *day - down*(day -1) >=high 니까 이항해서 day로 묶어보겠다.

day > (high - down )/ (up - down) 이다.

이건 day = high -down /up -down 하면 되는데 만약 이렇게 되면 나누어 떨어질때는 문제가 없는 식이지만 수식이 버림이 되니까 +1 을 해준다. 그러면 day = (high -down )/ (up - down) +1 하지만 여기서 문제가 또 생기는데 딱 나누어 떨어질때는 그냥 하나를 더 더해준게 되니까 여기에 위에 분자에 -1을 해주면 딱 나누어 떨어질때 문제를 해결 할 수 있다.

즉 day >= (high -down) /(up-down) 을 day = (high - down -1) /(up -down) +1 이 된다.

결국 정답 코드는 

#include<stdio.h>

int main()
{
	unsigned int up, down;
	unsigned int high;
	scanf("%d%d%d", &up, &down, &high); 
	unsigned int  day = (high - down -1) / (up - down) + 1;
	printf("%d", day);
}

이렇게 짧게 정리가 가능하다.

 

이 글은 코딩 꼬꼬마 시절에 푼 문제를 보관한 글로 네이버에 저장해둔 글을 옮긴 글입니다.
혹시나 참고하시는 부분에 이상한 부분이나 질문이 생긴다면 남겨주시면 친절히 답변 드리겠습니다.