[백준] 1339번 단어 수학

www.acmicpc.net/problem/1339

1339번: 단어 수학

무조건 높은 자리에 있는 알파벳이 큰 수인게 좋은 것이 아니다.

입력이 다음과 같이 들어오는 경우

10 
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

A가 100의 자리 수이므로 A가 클수록 좋다고 생각할 수 있지만

A=9, B=8이면 1780이지만 A=8, B=9이면 1790이다.

알파벳별로

1의 자리, 10의 자리, 100의 자리 순서대로 돌면서

1의 자리는 1의 자리수 * 1 한 것을 더해주고

10의 자리는 10의 자리수 * 10 한 것을 더해주고

100의 자리는 100의 자리수 * 100 한 것을 더해준다.

그러면 A는 100, B는 110이 나온다. 나머지 알파벳은 0이다.

이것을 내림차순으로 정렬하면 110, 100이다.

9부터 차례로 내려가면서 곱해주면 110 * 9 + 100 * 8 = 1790이 된다.

뭐가 A고 뭐가 B인지는 신경쓸 필요 없이 가장 큰 수부터 9와 곱하고 그 다음 큰 수와 8을 곱하고, ... 이런 식으로 하면 된다.

 

입력이 다음과 같이 들어오면

3
ABC
BAC
CCC

A, B, C가 뭐가 될지는 모르겠지만 110A + 110B + 113C를 한 것이 세 숫자의 합이다.

이 110A+110B+113C를 가장 크게 만드는 A, B, C를 찾기만 하면 된다.

그런데 뻔하지 않나? 113이 가장 크므로 C가 9가 되고 A, B가 8, 7이면 된다.

이것을 코드로 구현하기만 하면 된다.

 

코드대로 설명하자면 이차원 벡터 alphabetCount는 다음과 같을 것이다.

alphabet[i][j]의 의미는 빨간색 글씨와 같다.

이제 alphabetCount를 이용하여 tempSum을 채운다.

110, 110, 113을 tempSum에 저장해준다.

그 후 tempSum을 오름차순 정렬하면 다음과 같을 것이다.

num은 9부터 시작해서 1씩 감소하면서 tempSum의 뒤의 원소부터 곱해준다.

113 * 9 + 110 * 8 + 110 * 7 = 2667

2667이 정답이 된다.

 

또 다른 예제를 보자.

입력으로

2
GCF
ACDEB

이렇게 들어온다면

alphabetCount는 다음과 같을 것이다.

이렇게 10000, 1, 1010, 100, 10, 1, 100을 tempSum에 저장해준다.

tempSum 벡터를 오름차순으로 정렬하면

위와 같을 것이다.

이제 num을 9부터 1씩 줄여가면서 tempSum의 뒤의 원소부터 차례로 곱해나가면 된다.

10000 * 9 + 1010 * 8 + 100 * 7 + 100 * 6 + 10 * 5 +1 * 4 + 1 * 3 = 99437

정답은 99437이다.

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<vector<int>> alphabetCount(8, vector<int>(26, 0));
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = s.size() - 1; j >= 0; j--) {
			alphabetCount[s.size() - 1 - j][s[j] - 'A']++;
		}
	}
	vector<int> tempSum(26, 0);
	for (int j = 0; j < 26; j++) {
		for (int i = 0; i < 8; i++) {
			if (alphabetCount[i][j] != 0) {
				tempSum[j] += pow(10, i) * alphabetCount[i][j];
			}
		}
	}
	sort(tempSum.begin(), tempSum.end());
	int num = 9;
	int total = 0;
	for (int i = tempSum.size() - 1; i >= 0; i--) {
		if (tempSum[i] == 0)
			break;
		total += tempSum[i] * num;
		num--;
	}
	cout << total;
	return 0;
}