백준 1500 최대 곱 C++

https://www.acmicpc.net/problem/1500

 

처음에 백트래킹으로 해결하려다가 시간초과가 났다.

곱하는 수들의 차이가 적을수록 곱이 커지기 때문에 그것을 이용해서 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

ll s, k;
ll ans = -1;

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

	cin >> s >> k;

	ll a = s / k;
	ll b = s % k;

	ll ans = 1;

	for (int i = 0; i < b; i++) {
		ans *= a + 1;
	}
	for (int i = 0; i < k - b; i++) {
		ans *= a;
	}
	cout << ans;
};