백준 11947번: 이런 반전이 (C++)

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

11947번: 이런 반전이

 

풀이

처음에 문자열로 1부터 하나씩 계산해보려다가 n이 최대 10억이라서 시간초과가 난다고 생각이 들었다.

그래서 고등학교때 배웠던 함수의 최댓값을 활용했다.

우선, 정수 n을 4자리 수 abcd의 형태로 나타내고 식을 세워보았다.

이렇게 n과 F(n) 을 곱한다고 가정했을 때, 초항이 큰 수가 최댓값이 된다는 것을 알았고

a에 대한 2차원 함수를 그려보니

a가 4.5일 때, 최댓값이 된다. a는 정수이기 때문에 4 or 5 가 된다.

 

502 * 497 = 249,494

501 * 498 = 249,498

500 * 499 = 249,500

499 * 500 = 249,500
498 * 501 = 249,498

497 * 502 = 249,494

.

.

.

 

실제로 값을 계산해보니 499... * 500... 꼴이 가장 크고 숫자가 더 커지면 작아진다.

그래서 앞자리가 5이상이면 499... * 500... 꼴로 계산을 해주었고

앞자리가 5보다 작다면 a * (9 - a) * 10 ^ i 으로 F(n)을 구해서 n을 다시 숫자로 변환시켜서 사랑스러움을 구해주었다.

 

 

전체 코드

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

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

	int T;
	cin >> T;

	while (T--) {
		string N;
		cin >> N;
		long long love = 0;

		if (N[0] >= '5') {
			love = 5 * pow(10, N.size() - 1) * (5 * pow(10, N.size() - 1) - 1);
		}
		else {
			for (int i = 0; i < N.size(); i++) {
				love += (9 - ((long long)N[i] - '0')) * pow(10, N.size() - i - 1);
			}
			love *= stoi(N);
		}
		cout << love << '\n';
	}
}