11947 이런 반전이

처음에 문제 제대로 안 읽고 풀다가 그냥 사랑스러움 값만 변환하는 함수만 작성했다.

알고보니 사랑스러움의 최댓값을 구하는 게 문제였다. 

 

1부터 n까지 최댓값을 어떻게 구해야 할까?

 

시도1

1에서 10^9까지 미리 구해둔 다음에 테케 들어올 때마다 뽑아 쓴다.

단점 : 시간복잡도와 메모리 둘 다 터진다.

 

 

그래서 조금 더 생각해보니 곱셈에서 최댓값은 두 수의 차가 최소가 되면 됐다. 

 

 

그 다음에 다시 중앙값 계산하는 함수를 작성했다. 각 자리수 별 중앙값을 반환하는 함수를 만들어 n이 이 보다 작으면 그 수로 사랑수 구하고 크다면 중앙값을 곱했다. 

 

쉬운 문제인 것 같은데 왜이리 애먹지?

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 1000000

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

i64     check_mid(i64 n)
{
    i64 max_num = 1;

    string s = to_string(n);
    for (int i = 0; i < s.size(); i++)
        max_num *= 10;

    return max(max_num / 2 - 1, 0ll);
}

i64     func(string s)
{
    string tmp = "";

    for (int i = 0; i < s.size(); i++)
        tmp += '9' - s[i] + '0';

    return stol(tmp);
}

int     main()
{
    int t;
    scanf("%d", &t);

    for (int i = 0; i < t; i++)
    {
        i64 n;
        scanf("%lld", &n);

        i64 res = check_mid(n);

        if (res < n)
            printf("%lld\n", res * (res + 1));
        else
            printf("%lld\n", n * func(to_string(n)));
    }

    return 0;
}