[C++] 백준 17828 문자열 화폐

#include <iostream>
#include <string>
 
using namespace std;
 
int n,x;
string answer = "";
 
void input() {
    cin >> n >> x;
}
 
void solve() {
    // 불가능한 경우 
    if(n * 26 < x || n * 1 > x) { cout << "!"; return; }                                                
    
    int s = n;
    
    for(int i=0; i<s; i++) {
        int n_tmp = n-1;
        
        if(n_tmp * 26 >= x-1) {
            answer += "A";
            x -= 1;
        }
        else {
            int tmp = x - n_tmp * 26;
            char c = 'A' + (tmp-1);
            answer += c;
            x -= tmp;
        }
        n -= 1;
    }
    
    cout << answer;
}
 
int main() {
    input();
    solve();
    
}

 

 

문자열 + 그리디 문제

 

N이 5,000,000 까지 가능하므로 O(n) 으로 처리하며 사전순으로 가장 앞서는 로직을 구현해야한다.

 

제출 후 50%에서 출력 초과가 났을 경우 n = 1, x = 100 의 반례를 생각해보자