c++ 백준_1132_"합"

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

1132번: 합

예제 1번을 예로 들어

​

ABC

BCA

를 더하면

(A+B) + (B+C) + (C+A)

100 10 1

각 자리수를 나타나게 된다

ABC를 변수 취급하고

저 자리수들의 합을 계수 취급했다.

​

그래서

A : 101

B : 110

C : 11

(이하 cost 라 칭하겠습니다)

​

그래서 저 수를 내림차순으로 정렬해

B : 110 * 9

A : 101 * 8

C : 11 * 7

​

더하면 1875 가 나온다.

이러한 방법을 진행했는데

​

​

예제 3 번의 경우

ABCDEFGHIJ

J

여기서 모든 숫자는 0으로 시작하지 않기 때문에 J는 0이 되면 안된다.

​

0이 되는 경우는 987...210 총 10자리수 이상일 때만

0이 나올 수 있다.

​

그래서 0 이 되면 안되는 알파벳을 미치 체크해두고

숫자 자리수 크기가 10이상이고,

예제 1번처럼 내림차순 정렬했을 때

맨 마지막에 위치하는 알파벳이 0이 되면 안될 때

현재 알파벳 중 맨 마지막 알파벳 제외 가장 작은 수( cost가 가장 작은 수)와 교체하였습니다.

​

​

처음에 왜 자꾸 안되지했는데

A~J 길래 최대 길이가 10일 줄 알았다.

문제를 잘 읽자

this is maximum 12자리 baby

 

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

int main(void) {
	int n;
	cin >> n;

	vector<string> str(n);
	vector<bool> not_zero(10, false);

	int size = 0;
	for (int i = 0; i < n; i++) {
		cin >> str[i];
		if (size < str[i].size())
			size = str[i].size();
		not_zero[str[i][0] - 65] = true;
	}

	vector<string> ch(size, "");
	vector<pair<long long, char>> alpha(10);
	char c = 'A';
	for (int i = 0; i < 10; i++) {
		alpha[i] = { 0,c };
		c++;
	}

	for (int i = 0; i < n; i++) {
		string temp = str[i];

		for (int j = size - 1; j >= 0; j--) {
			ch[j] += temp.back();
			temp.pop_back();
			if (temp.size() == 0)
				break;
		}
	}

	long long p = 1;
	for (int i = size - 1; i >= 0; i--) {
		string temp = ch[i];

		for (int j = 0; j < temp.size(); j++) {
			alpha[temp[j] - 65].first += p;
		}
		p *= 10;
	}
	sort(alpha.begin(), alpha.end(), greater<>());

	if (not_zero[alpha[9].second - 65] && size >= 10) {

		int index = -1;
		long long value = alpha[0].first; // 임의의 큰 수
		for (int i = 0; i < 10; i++) {
			if (!not_zero[alpha[i].second - 65] && value >= alpha[i].first) {
				value = alpha[i].first;
				index = i;
			}
		}
		swap(alpha[index], alpha[9]);
		sort(alpha.begin(), alpha.end()-1, greater<>());
	}


	int i = 0;
	p = 9;
	long long sum = 0;
	while (i < 10) {
		if (alpha[i].first == 0)
			break;
		sum += (alpha[i].first * p);
		p--;
		i++;
	}
	cout << sum;

}