8월 1일(월) - 7단계(2869번)

7단계 - 2869번

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

 

문제점

1. 첫 번째 제출은 초반에 함수를 설정하려던 "int climbing(a, b);" 부분을 삭제하지 않아서 컴파일에러가 발생

해당 부분 삭제 후  두 번째 체출하자, 시간초과가 발생

-> 문제를 풀면서 시간제한 때문에 오류가 발생한 적은 없기에 도저히 무슨 문제인지를 모르겠어서 검색

-> 반복문을 사용했기 때문에 시간오류가 발생했다는 점을 알게되었다

 

2. 반복문으로 풀어서 시간초과가 발생하며 a,b,v 등의 변수의 최대가 10억이기 때문에 수식을 세워서 풀이

-> v-b-1 / a-b 값에 +1 을 해주며 date 변수값을 계산

 

////////////////////////////////////////////////

+) 찾다보니 문제의 분류자체가 binary search에 속해있기에, 이진탐색을 이용한 풀이도 가능하다는 것을 발견했다

출처: https://ggodong.tistory.com/169

////////////////////////////////////////////////

 

두 번째 제출풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
	int a, b, v;
	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &v);

	int date = 0;
	int distance = 0;
	
	while (a<v)
	{
		date++;

		distance = distance + a;
		if (distance >= v)
		{
			break;
		}

		else if (distance - b >= v)
		{
			break;
		}

		else
		{
			distance = distance - b;
		}
	}

	printf("%d", date);
	return 0;
}

 

최종풀이 - 1 (수식 계산)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
	int a, b, v;
	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &v);

	int date = 0;
	int distance = 0;
	
	date = (v - b - 1) / (a - b) + 1;
	printf("%d", date);

	return 0;
}

 

최종풀이 - 2 (binary search)

출처: https://ggodong.tistory.com/169

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

long long A, B, V;
long long y1, y2, mid = 0, result = 0;

void binarySearch(long long left, long long right) {
	if (left <= right) {
		mid = (left + right) / 2;
		y2 = mid * (A - B);
		y1 = y2 + B;
		if (y1 < V) {
			binarySearch(mid + 1, right);
		}
		else {
			result = mid;
			binarySearch(left, mid - 1);
		}
	}
}

int main(void) {
	scanf("%lld %lld %lld", &A, &B, &V);
	long long left, right;
	left = 1; right = (V / (A - B)) + 1;
	binarySearch(left, right);
	printf("%lld", result);
}

(binary search는 강의시간에만 배웠지, 실제로 문제풀이에 사용해본 적이 없고, 적용되는것도 처음봤다...)

 

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