BOJ 26651 : 팬램그

• 문제 링크 : boj.kr/26651
• 난이도 : G5
• 태그 : 수학, 해 구성하기

26651번: 팬램그

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    ll x;
    cin >> x;
    if(x == 0) {
        cout << "LICKELON";
        return 0;
    }
    ll a = 0;
    while(a*a <= x) {
        a++;
    }
    a--;
    ll b = a;
    while(a*b <= x) {
        b++;
    }
    b--;

    for(int i = 0; i < a; i++) cout << "A";
    cout << "BCDEFGHIJKLMNOPQRSTUVWXY";
    for(int i = 0; i < b; i++) cout << "Z";

    ll c = x - a*b;
    for(int i = 0; i < c; i++) cout << "A";
    cout << "BCDEFGHIJKLMNOPQRSTUVWXYZ";

    return 0;
}

---

풀이

A~Z가 순서대로 연속해 있고, 각 문자가 1개 이상인 문자열을 T라고 하자. 이 문자열에서 그램팬인 부분 문자열은 A의 갯수 * Z의 갯수이다.

또한 $T_1T_2\cdots$인 문자열이 있다고 했을 때 전체 문자열에서 그램팬인 부분 문자열은 부분 T의 갯수의 합과 같다.

 

X를 a*b로 나타내면 될 것처럼 보이지만, X의 1을 제외한 가장 작은 약수가 50000보다 크다면 문자열의 길이가 조건을 넘게 된다.

 

X를 a*b+c로 나타내 보자. a를 $a*a \leq X$인 최댓값, b를 $a*b \leq X$인 최댓값으로 잡마보자. X의 범위에 의해 $a \leq 31622$, $b \leq 31623$이다. $c \leq a$이므로 이 문자열의 전체 길이는 $a+a+a+52 \leq 94918$를 넘지 않는다.