[C++][수학1 - 달팽이는 올라가고 싶다(2869)] 시간 제한

백준 달팽이는 올라가고 싶다 바로가기

 

백준 체점 결과

 

 

※시간 제한 0.15초라는 것에 주의

 

 

[첫 번째 풀이] => 시간 초과

#include <iostream>

using namespace std;

int main(void){

	int up,down,len,day=0;
	cin >> up >> down >> len;
	day = len / (up - down);

	cout << day - 1;
	return 0;
}

이 문제의 제한 시간은 0.15초이다. 루프를 사용하기엔 부족하다.

 

 

[두 번째 풀이] => 실패

#include <iostream>

using namespace std;

int main(void){
	int up, down, des,day;
	cin >> up >> down >> des;
	day = ceil((float)des / (up - down))-1;
		if (des == up) day=1;	
	return 0;
}

일부 케이스에서 성립이 안된다.

 

 

[세 번째 풀이]

#include <iostream>

using namespace std;

int main(void){
	int up, down, des,day;
	cin >> up >> down >> des;
	day =(des - up) % (up - down) == 0 ? (des - up) / (up - down) + 1 : (des - up) / (up - down) + 2;
	return 0;
}

 

 

풀이 전략

1.먼저 예제 케이스들을 만들었다.

up	down	des	day	(des-up)/(up-down)
3	1	10	5	7/2 = 3.xx
4	1	10	3	6/3=2
2	1	5	4	3/1=3
5	4	5	1	0/1=0
2	1	5	4	3/1=3

2.문제를 보면 정상을 올라간 후 미끄러진다는 것에서 힌트를 얻었다.

두 번째 풀이에서 이 부분에서 좀 잘 맞지 않아 틀렸다.

그러니까 일단 올라가야하는 높이(des)에서 낮에 올라가는 높이(up)를 뺀다. : des - up

그 다음 하루에 올라갈 수 있는 높이 : up - down

나눈다.

(des-up)/(up-down) 값을 구해서 상황을 본다.

 

3. (des-up)/(up-down) ==  0  : 몫 + 1 (des에서 up을 빼줬으니 하루를 더해야한다.)

   (des-up)/(up-down) !=  0  : 몫 + 2 (des에서 up을 뺀 하루와 up-down이하의 높이를 더 올라가야하므로 2를 더함)

그니까 나누어 떨어지지 않는 다면 up과 up-down보다 작은 높이를 더 올라가야하므로 2를 더한다.

 

 

참고 페이지

달팽이 참고 페이지