c++ 3일차

8단계 수학1. 

수학문제를 풀면서 사고력을 길러보자,,,, 이런 뜻인줄 몰랐죠,,,,

최대한 수학을 이용해서 빠르고 효율적으로 풀어야만 한다. ಥ_ಥ

 

백준1712번 (www.acmicpc.net/problem/1712)

 

#include<iostream>
using namespace std;

int main() {
	long a, b, c;
	cin >> a >> b >> c;
	
	if (b >= c) cout << -1;
	else cout << a / (c - b) + 1;
}

판매대수를 i 라고 하면  a+ b*i < c*i 가 되는 그 순간이 손익분기점이겠구나! 라고 생각하고 

손익 분기점이 영영 나지 않는 상황은 지금 a+bi , ci를 일차함수로 바라보면 둘이 만나지 않아야하니깐 평행하거나 b보다 c의 기울기가 더 작은 경우(음수에서 만나니깐)일거다.

그래서 b>=c인 상황에는 -1을 반환하고 while문을 통해서 찾으니 시간초과..^_^... 

시간초과ㅏ라는 키워드는 별로 친숙하지 않아서 질문 검색을 해보니 부등식을 잘 이용해서 최소화 해야한다고 한다. 

 b < c일 때, 두 일차함수가 만난 이후의 최소의 정수가 답이다 . a+bi = ci 라고 두면 만나는 점은 a / c-b이다.

근데 요 자식이 정수일지 실수일지 모른다 

만약 실수라면 지금 변수타입이 long이니까 소수점 버린 정수로 바뀔거다 3.2라면 3으로!

근데 우리가 필요한 값은 3.2 이후의 최소 정수 4니깐 1을 더해주면 된다.

 

ㅇㅣ 문제 풀고 살짝 쫄았다 ㅠ

 

백준2839번(www.acmicpc.net/problem/2839)

#include<iostream>
using namespace std;

int main() {
	int weight, x, y, res=0;
	cin >> weight;
	
	//5x+3y = weight
	if (weight % 5 == 0) cout << weight / 5;
	
	else {
		for (int i = weight / 5; i >= 0; i--) {
			if ((weight - 5 * i) % 3 == 0) {
				x = i;
				y = (weight - 5 * x) / 3;
				res = x + y;
				cout << res;
				break;
			}
		}
		if (res == 0) cout << -1;
	}
}

 윗문제 떄문에 엄청 쫄아서 어렵게 접근했는데 그러면 코드가 안짜지더라 ㅎ하하하ㅏ하

그냥 심플하게 최대한 적은 수를 만드려면 5kg짜리가 많아야 한다

그래서 5kg를 기준으로 제일 많이 넣을 수 있는 갯수부터 0개까지 줄여와보자.

1. 무게가 5의 배수라면? 개꿀이당 그냥 5kg짜리만 왕창 들고가면 되기때문이다.

2. 5의 배수가 아니라면 ? 사실 이런 상황이 더 많을 것이다. 

가장 많이 가져갈 수 있는 숫자는 무게/5 일거다. 거기서부터 시작해서 0까지 5kg짜리의 개수를 하나하나 늘리면서 3kg짜리를 살펴보자

weight - 5 * (5kg 개수 ) 했을 때 이게 3의 배수여야 3kg짜리를 가져갈 수 있다. 

맨 처음에는 막 경우의 수를 기록해두고 그 중 최댓값을 생각했는데 코드도 못 짜겟고, 곰곰히 생각해보면 그냥 5kg의 개수가 가장 크고 , 3kg의 개수가 가장 적을 때가 전체 갯수가 최대일때다. 마침 5kg개수가 가장 클 때부터 세고 있으니, 그냥 wight - 5 * i가 딱 3의 배수가 나올 때 그때가 전체가 최소 개수인거다. 이때 res값을 바꿔주자.

for문을 다 돌았는데도 res값이 안바뀐 상태 즉 0이라면 조합이 안나왔다는 뜻이니 -1을 반환하자.