[백준] 17828 - 문자열 화폐

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

17828번: 문자열 화폐

 

사전 순으로 앞서는 문자열을 구하기 위해,

문자열의 앞부분부터 가능한 한 가장 작은 문자열을 이어 붙인다.

여기서 가능한 한 가장 작은 문자열이란? 예제 입출력 1을 살펴보자.

6 64
AAAIZZ

 

A...... -> 화폐 가치 = 1, 남은 화폐 가치 = 63, 남은 화폐 수 = 5

AA.... -> 화폐 가치 = 2, 남은 화폐 가치 = 62, 남은 화폐 수 = 4

AAA... -> 화폐 가치 = 3, 남은 화폐 가치 = 61, 남은 화폐 수 = 3

AAAA.. -> 화폐 가치 = 4, 남은 화폐 가치 = 60, 남은 화폐 수 = 2 -> X

마지막에서 남은 화폐 가치는 60이면서 남은 화폐 수는 2이다. 그렇다면 화폐 가치가 최소 30인 화폐가 존재해야 하는데 최대 화폐 가치는 26이므로 불가능하다.

따라서 A-Z까지 가능한 경우의 수를 전부 따져보면 된다.

 

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, x;
    cin >> n >> x;
    if (n * 26 < x || n > x) {
        cout << "!";
        return 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= 26; j++) {
            if (x - j <= (n - i - 1) * 26) {
                x -= j;
                cout << (char)(j - 1 + 'A');
                break;
            }
        }
    }
}