[BOJ/백준] C++ 2839번 설탕 배달 문제 풀이 (방정식 세워서 풀기)

문제

풀이

✔️ 방정식을 이용하면 쉽게 풀 수 있다.
N을 입력받은 수라고 할 때,
N = 5x + 3y
라고 두고 코드를 작성해 가면 어렵지 않게 풀어낼 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N = 0;
	int numi = 0;
	int numj = 0;
	int cnt = 0;

	// 입력받기
	cin >> N;

	// 최적의 i와 j의 값을 구하기
	for (int i{ 0 }; i <= 1000; i++) {
		for (int j{ 0 }; j <= 1666; j++) {
			if (N == 5 * i + 3 * j) {
				cnt++;
				numi = i;
				numj = j;

			}
			else
				continue;
		}
	}

	if (cnt != 0) {
		cout << numi + numj;
	}
	// N = 5x + 3y 방정식에 맞는 x,y 쌍을 찾지 못했을 때 
	else
		cout << -1;
}

코드에서 i <= 1000 , j <= 1666 인 이유

✔️ N에 대한 조건을 살펴보면 3 ≤ N ≤ 5000 이다.

• x가 가질 수 있는 최대값 : 5000 / 5 = 1000
• y가 가질 수 있는 최대값 : 5000 / 3 = 1666