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

---

문제

---

풀이

 이 문제를 풀면서 참 많은 고난이 있었다.. 세 번째 풀이만에 성공했고.. 문제를 풀면서 화난 치와와가 된 기분을 느꼈다..

첫 번째 코드 - 실패 

 ➡ 시간복잡도: O(n), while문 사용

 

처음에는 단순하게 A만큼 증가하고, B만큼 감소하는 while문을 만들어 높이 변수 height가 V에 도달하면 break 되도록 했다.

하지만, 시간 초과가 발생했다.

 

//첫 번째 시도_ O(n), 시간초과

#include <iostream>
#include <string>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	int A, B, V, height = 0, day = 0;
	cin >> A >> B >> V;

	while (1) {
		height += A;
		++day;
		if (height >= V) {
			break;
		}
		height -= B;
	}

	cout << day;

	return 0;
}

 

 

 

 - 시간 초과 이유: 반복문을 사용해, O(n)의 시간복잡도를 갖는다. 따라서, 시간이 너무 오래 걸린다.

 

이 문제는 시간 제한이 0.25초이기 때문에 반복문을 사용하면 시간이 초과된다.

예를 들어, A = 1000, B = 999, V = 1000000 인 경우라면, 아래처럼 999001일이 걸린다.

만약, 반복문을 사용하면 오르락 내리락을 대략 999000번 반복하므로 시간 초과가 발생하는 것이다.

추가로, 이 코드에서는 (A >= V)인 조건도 고려하지 않았다.

  

 

 

---

두 번째 코드 - 실패 

 ➡ 시간복잡도: O(n), while문 사용

 

식으로 풀어야겠다고 생각하여, (A - B)씩 증가하는 것으로 접근해 풀었으나 결론적으로는 또 반복문을 써서 시간초과가 발생했다. 이 코드도 (A >= V)인 조건을 추가하지 않았지만, 다른 반례들은 모두 통과했다. 그냥 더 복잡하고 똑같이 시간초과가 나는 코드를 만들어냈다..

 

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int A, B, V, height = 0, day = 0, before, semibefore;
	cin >> A >> B >> V;

	before = A - 2 * B;
	semibefore = A - B;
	while (1) {
		height += (A - B);
		day++;
		cout << day << endl;
		if (height >= V) {
			height -= before;
			day--;
			cout << day << "   ";
			while (1) {
				if (height <= V) {
					break;
				}
				height -= semibefore;
				day--;
				cout << day << "   ";
			}
			break;
		}
	}

	cout << day;

	return 0;
}

 

따라서, 마지막 풀이에는 절대 반복문을 쓰지 않기로, 시간 복잡도 O(1)로 풀기로 다짐하고 다시 도전했다.

 

---

세 번째 코드 - 성공  

 ➡ 시간복잡도: 드디어 O(1)!

 

 조건을 세 가지로 나누었다.

 

 1. A가 V보다 크거나 같은 경우 - 달팽이가 하루만에 나무를 올라가므로, 항상 하루 소요

	if (A >= V) {
		cout << "1";
	}

 

 

 2.  A가 V보다 작은 경우: 나무의 높이인 V에서 달팽이가 일어나있는 동안 올라가는 높이인 A를 뺀 값을 활용했다.

 

 2-1. 만약, (V - A)에서 (A - B)를 나눈 나머지가 0이라면, (A - B) x ( Day ) + A = V 일 것이다.

예를 들어, A = 3, B = 2, V = 7 인 경우라면, (3 - 2) x ( Day ) + 3 = 7이다.

Day = 4지만, A만큼 올라간 하루를 더 추가해주어야 한다.

 

	else if ((V - A) % (A - B) == 0) { // 나머지 == 0이라면, 딱 A만큼 더 가면 V에 도달하므로 +1을 해준다.
		cout << ((V - A) / (A - B) + 1);
	}

 

 

 2-2. 만약, (V - A)에서 (A - B)를 나눈 나머지가 0이 아니라면, (A - B) x ( Day ) + (A - B) + (A보다 적은 길이) = V 이다.

Day에서, (A - B)만큼과 (A보다 작은 수)만큼 더 올라가므로 이틀을 더 추가해주어야 한다.

 

	else if ((V - A) % (A - B) != 0) { // 나머지 != 0이라면, (A-B)만큼 한 번더 올라간 후 A보다 작은 높이가 남은 것이므로 +2
		cout << ((V - A) / (A - B) + 2);
	}

---

정답 코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int A, B, V;
	cin >> A >> B >> V;

	if (A >= V) {
		cout << "1";
	} 
	else if ((V - A) % (A - B) == 0) {	// 나머지 == 0이라면, 딱 A만큼 더 가면 V에 도달하므로 +1을 해준다.
		cout << ((V - A) / (A - B) + 1);
	}
	else if ((V - A) % (A - B) != 0) {	// 나머지 != 0이라면, (A-B)만큼 한 번더 올라간 후 A보다 작은 높이가 남은 것이므로 +2
		cout << ((V - A) / (A - B) + 2);
	}


	return 0;
}

---

결과