백준 1712번 c++

원래 알고리즘 문풀한건 안올리는편인데

이번 문제는 너무 재밌어서 올려보려고한다

정리하자면

A B C가 주어지고

A + B*N <C*N을 만족하는

N을 구하는 거다

N이 존재하지않으면 -1을 출력한다.

 

만족하는 N이 존재하려면 C>B여야한다

그래야지 N이 커질수록 A+B*N을 C*N이 초과할수있다

 

 

 

처음 코드제출

시간초과가났다

#include <iostream>

using namespace std;


int main() {

	// a b c
	// a+b*n<c*n
	long long start, result=-1;
	int a, b, c;
	cin >> a;
	cin >> b;
	cin >> c;

	if (b > c) {
		cout << -1 << endl;
		return 0;
	}

	
	start = a / c;

	for (long long i = start; i <= 2100000001; i++) {
		if (a + b * i < c * i) {
			result = i;
			break;
		}
	}

	cout << result;

	return 0;
}

반복문의 초기식을 A/C를 해주고

조건식은 21억이하

증감식은 1씩증가

이렇게 해서 0부터 시작안하면

반복문 시간을 줄일 수 있을거라했는데도

21억이라는 수는 너무 컸다

 

 

그래서 고민하다가

반복문으로는 못풀겠구나

식을 건드려봐야겠다고

생각했다

 

(b-c)는 음수이다

c가 b보다 커야 i가존재하기때문이다

그래서 오른쪽으로 넘겨도 부등호의 방향은 변하지 않는다

신기하게도 i로 묶고 식을 넘겨서 정리하니까

a/(c-b)<i 라는 식이나온다

즉 i는 a/(c-b)+1이 된다

너무 신기하지않나?

마치 수학문제를 푸는것같았다

 

 

 

 

2번째 코드제출

런타임 에러 (DivisionByZero)

#include <iostream>

using namespace std;


int main() {

	// a b c
	// a+b*n<c*n
	long long start, result=-1;
	int a, b, c;
	cin >> a;
	cin >> b;
	cin >> c;

	if (b > c) {
		cout << -1 << endl;
		return 0;
	}

	
	result = a / (c - b) + 1;

	cout << result;

	return 0;
}

b==c인 경우를 고려하지않았다

 

 

 

 

세 번째 코드 제출

정답!!

#include <iostream>

using namespace std;


int main() {

	// a b c
	// a+b*n<c*n
	long long start, result=-1;
	int a, b, c;
	cin >> a;
	cin >> b;
	cin >> c;

	if (b >= c) {
		cout << -1 << endl;
		return 0;
	}

	
	result = a / (c - b) + 1;

	cout << result;

	return 0;
}

반복문으로 접근하지 않고

식을 정리하는 방식으로 풀리는 문제였다