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

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

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

오답 코드

 

처음에는 시간 초과로 인해 실패했고, 코드는 다음과 같다.

#include<stdio.h>

main() {
	int a, b, v, h = 0, day;		//h: 현재까지 올라온 높이, day: 일수
	scanf("%d %d %d", &a, &b, &v);
	for (day = 1; h < v; day++) {
		h += a;
		if (h >= v)
			break;
		else
			h -= b;
	}
	printf("%d", day);
}

a만큼 올라간 후, v만큼 도달하지 못했으면 b만큼 떨어지고, v에 도달했으면 반복문을 빠져나온다.

 

 

정답 코드

#include<stdio.h>
main() {
	int a, b, v, day = 0;	
	scanf("%d %d %d", &a, &b, &v);
	if ((v - b) % (a - b) == 0)
		day = (v - b) / (a - b);
	else
		day = (v - b) / (a - b) + 1;
	printf("%d", day);
}

 

설명

 

시간 초과로 실패한 이후 케이스를 나눠야겠다고 생각했다.

a만큼 올라가고 b만큼 떨어지므로 하루에 가는 거리는 a-b이다.

그런데 이렇게 하면 마지막날(목표에 도달한 날)에도 b만큼 떨어진다.

따라서 이를 고려해 v-b만큼 간다고 생각하고, 다음과 같이 케이스를 나눴다.

 

1. v-b가 a-b로 나누어 떨어지는 경우

2. v-b가 a-b로 나누어 떨어지지 않는 경우

 

1의 경우에는 v-b를 a-b로 나누었을 때 몫이 곧 움직인 일수(day)가 되고, 2의 경우에는 거기에 +1을 해주었다.

이렇게 하면 시간 제한에 걸리지 않고 올바른 값이 출력된다.