#37. [백준_C언어] 2869 : 달팽이는 올라가고 싶다

 

 입력 코드 

#include <stdio.h>

main() {
	int A, B, V;
	scanf("%d %d %d", &A, &B, &V);

	int d;
	d = (V - B - 1) / (A - B) + 1;

	printf("%d\n", d);
}

 

 코드 설명 

#수학 #시간초과 

#include <stdio.h>

main() {
	int A, B, V;
	scanf("%d %d %d", &A, &B, &V);

	int i=0, p=0;

	while(1){
		if (p < V) {
			if (i % 2 == 1)
				p += A;
			else if (i % 2 == 0)
				p -= B;
		}
		else if (p >= V) {
			printf("%d\n", i);
			break;
		}
		i++;
	}
}

처음에는 현재 위치(p)가 V보다 작을 때와 크거나 같은 경우를 나누고 p<V일 때 홀수번일 때와(낮) 짝수번일 때(밤)를 나누어서 A만큼 올라갔다가 B만큼 내려오도록 했는데 횟수로 나누어서 결과값이 크게 출력되었다.

 

낮+밤 = 하루인 것을 놓친 것이다. 그래서 마지막에 i/2 값으로 출력하려고 했으나 그것도 정확한 값이 출력되지는 않았다.

#include <stdio.h>

main() {
	int A, B, V;
	scanf("%d %d %d", &A, &B, &V);

	int i=1, p=0, d;

	while(1){
		if (p < V) {
			if (i % 2 == 1) {
				p += A;
				d = i / 2+1;
			}
			else if (i % 2 == 0) {
				p -= B;
				d = i / 2;
			}
		}
		else if (p >= V) {
			printf("%d\n", d);
			break;
		}
		i++;
	}
}

그래서 새로운 문자 d(=ans) 변수를 설정해서 출력하려고 했으나 시간 초과로 실패했다. 찾아보니까 반복문을 사용하면 100% 시간 초과가 되는 문제였다. 그래서 한 줄 수식이나 이분 탐색으로 풀어야 된다고 한다.

 

#include <stdio.h>

main() {
	int A, B, V;
	scanf("%d %d %d", &A, &B, &V);

	int d;
	d = (V - B - 1) / (A - B) + 1;

	printf("%d\n", d);
}

 

달팽이는 하루에 A-B 만큼 올라가고 마지막 날에 올라가고 나서는 미끄러지지 않는다. 그래서 총 올라가야 하는 것은 V-B이지만 만약 V-B가 A-B로 나누어 떨어지지 않는다면 (V-B)/(A-B) 보다 +1 한 것이 정답일 것이다. 

 

예를 들어, A=3, B=2, V=5이면 하루에 1(A-B)씩 올라가는 셈이고 올라가야 하는 것은 3(V-B)이다.

 

그래서 첫째날 1, 둘째날 2, 셋째날 3, 넷째날 4이지만

넷째날 낮에 이미 5를 올라가기 때문에 더 이상 미끄러지지 않고 답이 4가 되는 것이다.

→ (V-B)/(A-B)+1 = 3/1+1 = 4가 되는 것이다.

 

그런데 그냥 (V-B)/(A-B)+1 를 해버리면 나누어떨어지지 않는 경우 값이 정확히 나오지 않기 때문에 (V-B-1)/(A-B)+1 을 해준다.

 

 

 

↓↓↓ 참고한 사이트

yahohococo.tistory.com/28

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

 

 

 문제 출처 

www.acmicpc.net/problem/2869

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