[BOJ] 17828 : 문자열 화폐 (C++)

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

17828번: 문자열 화폐

걸린 시간 : 24분 6초

---

오류 코드

맨 처음, A와 Z를 하나하나 문자열에 더해가면서 했다. 뭔가 비효율적이라고 생각이 들었고, 역시나 시간초과였다.

#include <bits/stdc++.h>
using namespace std;

int N, X;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> X;
	if (N > X || N * 26 < X) {
		cout << "!";
		return 0;
	}
	X -= N;
	string ans = "";
	while (X > 0) {
		if (X >= 25) {
			ans = 'Z' + ans;
			X -= 25;
		}
		else {
			ans = (char) ('A' + X) + ans;
			X = 0;
		}
	}
	while (ans.size() < N) ans = 'A' + ans;
	cout << ans;
	return 0;
}

알고리즘

그리디 문제이다. A의 개수와 Z의 개수와 그 중간에 오는 문자를 따로따로 구해서, A 개수만큼 출력, 중간 문자 출력, Z 개수만큼 출력 하면 된다.

하지만 2가지에 주의해야 한다.

1. A...A 로도 안되는 경우, Z...Z 로도 안되는 경우 먼저 생각해주고 예외처리
2. 중간 문자가 B~Y 가 아니라 A 혹은 Z 인, 즉 A와 Z로만 문자열이 이루어진 경우는 middle 값에 0이 들어가므로 따로 생각해줘야 한다.

#include <bits/stdc++.h>
using namespace std;

int N, X;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> X;
	if (N > X || N * 26 < X) {
		cout << "!";
		return 0;
	}
	X -= N;
	int numA, numZ, middle;
	numZ = X / 25;
	middle = X % 25;
	if (middle == 0)
		numA = N - numZ;
	else
		numA = N - numZ - 1;
	for (int i = 0; i < numA; i++)
		cout << "A";
	if (middle != 0)
		cout << (char) ('A' + middle);
	for (int i = 0; i < numZ; i++)
		cout << "Z";
	return 0;
}