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

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

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

출력

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

---

풀기 전 로직 생각

1. 나무높이 , 낮에 올라가는 높이, 밤에 미끄러지는 높이를 입력받는다.
2. 현재 올라가있는 높이를 0으로 초기화하고 낮에 올라간 높이만큼 더한 후 그 높이가 나무높이보다 크거나 같으면 종료시키고 아닐경우 밤에 미끄러질 높이만큼 빼준 후 날을 증가시킨다.

코드

#include <iostream>
using namespace std;

int main() {

	int height; //나무 높이
	int day; //낮에 올라가는 높이
	int night; //밤에 미끄러지는 높이

	cin >> day >> night >> height;

	int count_day = 1;
	int now_height = 0;
	while (true) {
		now_height += day;
		if (height <= now_height) {
			break;
		}
		now_height -= night;
		count_day++;
	}

	cout << count_day;
	
	return 0;
}

 

---

풀고 난 후 찾아본 것

풀어보고 나서 이게 최적의 계산일까 하며 질문계시판도보고 검색해봤는데 최소한으로 단 한줄만에 계산이 되더라구요.. 알아갈수록 신기한 수학의 세계...

최소한으로 계산하는 로직

#include <iostream>
using namespace std;

int main() {

	int height; //나무 높이
	int day; //낮에 올라가는 높이
	int night; //밤에 미끄러지는 높이

	cin >> day >> night >> height;

	int raise = day - night; //순수 올라가는 높이
	int count_day = (height - day + raise - 1) / raise + 1; //최소한의 계산

	cout << count_day;
	
	return 0;
}

 

height - day를 하는 이유: 마지막 날에 달팽이가 낮에 정상을 도달하는 높이를 제외한 나머지 높이

 

raise : 하루 동안 달팽이가 실제로 올라가는 순수 높이

 

height - day + raise -1 : height - day를 나눌때, 나누어 떨어지지 않는 경우를 고려하기위해 -1을 해서 올림 효과를 내기 위함.

 

/ raise : 나머지 높이를 하루 동안 올라가는 순수 높이로 나눠서 며칠이 걸리는지 계산

 

+1 : 마지막날 더해준다.

 

 

 

 

아직 갈길이 멀다...