백준 1339번 단어 수학

< 백준 1339번 단어 수학 - 마포 코딩박>

사용한 알고리즘: 그리디..?


 알파벳으로 구성된 N개의 단어가 주어진다. 모든 단어에 쓰인 총 알파벳 종류는 10개 이하이다. 각 알파벳은 0~9 중 하나의 값을 갖을 수 있고, 서로 다른 알파벳은 같은 값을 갖을 수 없을 때, 단어들을 숫자로 변환해 더했을 때 최대값을 구하는 문제이다.

문제풀이는 다음과 같습니다.
(1) (코드: 12~19)
 단어가 주어지면, 각 알파벳이 몇개 있는지를 생각했습니다.
 예를들어 ABC가 주어지면, C는 1개, B는 10개, A는 100개 있는 것입니다.
 이에 따르면 ABC + BCD 인 경우는 A 100개, B 10+100개, C 1+10개, D 1개 있는 것이겠죠.

(2) (코드: 21~23)
 모든 단어을 각 알파벳별 개수로 저장한 후, 각 글자의 개수들을 sort해주었습니다.

(3) (코드: 25~29)
 개수가 많은 알파벳이 큰 Value를 갖으면 됩니다.
 예를 들어 모든 단어가 ABC , CA, DCB 로 주어져 모든 단어를 더하게되면, A 100+1개, B 10+1개, C 1+10+10 개, D 100개 가 더해지게 됩니다.
 따라서 A=9, D=8, C=7, B=6 으로 계산하면 덧셈의 최댓값을 구할 수 있습니다.

	#include <bits/stdc++.h>
	using namespace std;
	long long ans;
	long long N, arr[27];
	vector<long long> V;
	string S;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	// 글자를 개수 생각해서 저장
	for (int i = 0; i < N; ++i){
	cin >> S;
	int cnt = 1;
	for (int j = S.size()-1; j >=0; j--){
	arr[S[j]-'A'] += cnt;
	cnt*=10;
	}
	}
	// 각 글자수를 sort
	for (int i = 0; i < 27; ++i)
	if(arr[i]!=0) V.push_back(arr[i]);
	sort(V.begin(),V.end());
	// 글자수 많은게 높은 값을 갖게 함.
	int value = 9;
	for (int i = V.size()-1; i >= 0; i--){
	ans += V[i]*value;
	value--;
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 1339.cpp hosted with ❤ by GitHub