백준 17828 문자열 화폐

17828번: 문자열 화폐

문제

작년에 소수나라에 다녀온 하나는, 올해는 문자열나라로 관광을 가려고 한다. 문자열나라에서는 특이하게 알파벳 대문자로 구성된 문자열을 화폐로 사용한다.

문자열나라에서 'A'는 1의 가치, 'B'는 2의 가치, ..., 'Z'는 26의 가치를 가지고 있으며, 이 알파벳들을 붙여 화폐로 쓰일 문자열을 만든다. 예를 들어, "HONGIK"의 가치는 8 +15 + 14 + 7 + 9 + 11 = 64가 된다.

소수나라에서 특이한 화폐 때문에 큰 스트레스를 받았던 하나는, 이번에는 정확한 소비 계획을 세워 미리 문자열 화폐로 돈을 환전해가려고 한다. 하나가 가져갈 문자열은 딱 하나이며, 길이는 N이고, 가치는 X여야 한다. 그리고 물론 알파벳 대문자로만 이루어져 있어야 한다.

그런데 환전소에서는 사전 순으로 앞서는 문자열을 우선적으로 환전해준다고 한다! 여행 준비에 정신이 없는 하나를 위해, 조건을 만족하면서 사전 순으로 가장 앞서는 문자열 구해주자.

 

 

그리디 문제이다. 길이가 N이고 가치가 X가 될 수 있는 문자열중에서 사전 순으로 가장 앞서는 문자열을 구해야한다.

사전 순으로 가장 앞서는 문자열이 될려면 A가 최대한 많이 있어야한다.

 

예를들어

N = 5 , X = 50 이면

5자리 문자열은 이런식으로 만들 수 있다.

A가 5개 일때

AAAAA - 5

A가 4개 일때

AAAAB - 6

AAAAC - 7

...

AAAAZ - 30

A가 3개 일때

AAABZ - 31

AAACZ - 32

...

AAAZZ - 55

A가 2개 일때

AABZZ - 56

...

사전 순으로 가장 앞서는 문자열은 A가 최대한 많이 나와야 하므로 AAAA..A?ZZZ 이런식으로 Z를 써서 A의 자리가 많아지게 해야한다.(A와 Z를 제외한 다른 문자는 하나만 써야 사전순으로 앞설 수 있다.)

X가 N보다 작거나 N*26보다 큰 경우는 문자열을 만들 수 없으므로 "!" 를 출력해 주었다.

#include <iostream>
#include <string>
 
using namespace std;
 
int main(void)
{
    int n;
    int x;
    
    cin >> n >> x;
    string ans = "";
    
    int k = 0;    // Z의 개수
    int A = 0;    // A의 개수
    
    char h = '0';
 
    if (n <= x) {
        for (int i = n - 1; i >= 0; --i) {
            if (x - i <= 26) {
                A = i;
                h = 'A' + (x - i) - 1;
                break;
            }
            else {
                x -= 26;
                k++;
            }
        }
 
        for (int i = 0; i < A; ++i) {
            ans += 'A';
        }
        ans += h;
        for (int i = 0; i < k; ++i) {
            ans += 'Z';
        }
 
        if (h == '0') {
            cout << "!" << endl;
        }
        else {
            cout << ans << endl;
        }
    }
    else {
        cout << "!" << endl;
    }
    return 0;
}