[Baekjoon/백준][2869][C/C++] 달팽이는 올라가고 싶다

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

수학적 수식의 구현을 통하여 시간복잡도를 $O(1)$으로 줄이면 풀 수 있는 문제이다. 수학적 기법이 알고리즘의 실행시간에 얼마나 영향을 줄 수 있는지를 알려준다.

1. 문제

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

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

[문제]

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

[출력]

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

[예제 입력 1]

2 1 5

[예제 출력 1]

4

[예제 입력 2]

5 1 6

[예제 출력 2]

2

[예제 입력 3]

100 99 1000000000

[예제 출력 3]

999999901

2. 풀이

위 문제를 단순 반복문을 이용하여 $O(n)$ 시간내로 풀면 다음과 같다.

int main(int argc, char* argv[]) {
	/* Input */
	int A, B, V; scanf("%d %d %d", &A, &B, &V);
	int D = 0; // D는 Days(일수)를 뜻함.
	
	/* Calculate */
	while (true) {
		D++;
		V -= A;
		if (V <= 0)
			break;
		V += B;
	}

	/* Output */
	printf("%d", D);
    
	/* End */
	return 0;
}

Caculate 주석 안에 있는 내용을 살펴보자.

① 일수를 증가시킨다.

② A미터 올라간 만큼, 남은 나무 막대의 높이를 갱신한다.

③ 남은 나무 막대의 높이가 0 이하일 경우, 반복문을 탈출한다. (이때가 나무 막대를 모두 올라간 경우이다.)

④ B미터 내려간 만큼, 남은 나무 막대의 높이를 갱신한다.

 

단, 위 방법의 경우 시간초과로 오답처리 된다. 그렇다면 어떠한 방법으로 위 문제를 해결해야 할까?

 

반복문 안의 내용을 수식으로 단순화 시켜보자. Caculate 주석 안의 내용을 수식으로 바꾸면 다음과 같다.

$V - (A * D) + B * (D - 1) <= 0$

$V - AD + BD - B <= 0$

$-AD + BD <= B - V$

$D(-A + B) <= B - V (∵ B < A   i.e. -A + B < 0)$

$D >= (V - B) / (A - B)$

이때, 구하고자 하는 값은 위 조건을 만족하는 정수 D의 최솟값이므로, 아래의 값을 구하면 정답이 된다.

(int)ceil((double)(V - B) / (A - B))

3. 코드

#pragma warning(disable:4996)
#include <stdio.h>
#include <math.h>

int main(int argc, char* argv[]) {
	int A, B, V; scanf("%d %d %d", &A, &B, &V);

	printf("%d", (int)ceil((double)(V - B) / (A - B)));

	return 0;
}