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

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

문제

---

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

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

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

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

 

입력

---

첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다.

 

출력

---

첫 번째 줄에 조건을 만족하는 문자열 중, 사전 순으로 가장 앞서는 것을 출력한다. 만약 그런 문자열이 하나도 존재하지 않으면, "!"(따옴표 없이)를 출력한다.

 

문제 풀이

---

그리디 문제.

 

사전 순으로 가장 앞서는 것을 출력해야 하므로 가능한 한 맨 뒤쪽에 Z를 연속으로 두어야한다. 현재 붙일 글자를 제외하고, 현재 남은 글자 수와 해당 남은 글자 수로 만들 수 있는 최댓값이 몇인지 확인한다. 한 자릿수당 최댓값은 Z인 26이다. 예를 들어, 2자리가 남았다면 ZZ로 52가 최대가 된다.

남은 글자 수로 만들 수 있는 최댓값과 앞으로 만들 문자들의 문자열의 가치를 비교한다. 예를 들어, 현재 붙일 글자를 제외하고 2자리가 남았는데 남은 가치가 54이라면, 현재 붙일 글자는 가치가 54 - 52인 B가 된다. 남은 가치와 최댓값을 비교했을 때 남은 가치가 더 작다면, 남은 문자열을 모두 Z로 채운 가치보다 모자라다는 뜻이 된다. A를 붙여 사전 순으로 가장 앞서게 만든다.

 

불가능한 문자열은 가치가 문자열의 길이보다 작거나 모두 다 Z로 채운 경우인 26 * N보다 큰 경우이다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	long long N, X;
	cin >> N >> X;
	if (X < N || X > 26 * N)
	{
		cout << "!" << "\n";
	}
	else
	{
		string str = "";
		long long leftLetter = N - 1;
		long long leftMoney = X;
		for (int i = 0; i < N; i++)
		{
			long long maxMoneyOfLeft = leftLetter * 26;
			if (leftMoney - maxMoneyOfLeft > 0)
			{
				int index = leftMoney - maxMoneyOfLeft - 1;
				str += 'A' + index;
				leftMoney -= leftMoney - maxMoneyOfLeft;
			}
			else
			{
				str += 'A';
				leftMoney--;
			}
			leftLetter--;
		}
		cout << str << "\n";
	}
	return 0;
}