https://www.acmicpc.net/problem/1339
<코드>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
string s;
int n;
cin>>n;
vector<int>alpha(26);
for(int i=0;i<n;i++)
{
string s;
cin>>s;
for(int j=0;j<s.size();j++)
{
alpha[s[j]-'A']+=pow(10,(s.size()-1)-j);
}
}
sort(alpha.rbegin(),alpha.rend()); //내림차순 정렬
int num=9;
int sum=0;
for(int i=0;i<26;i++)
{
if(alpha[i]) // A~Z까지 값이 존재할 때
{
sum += (alpha[i] * num);
num--;
}
}
cout<<sum<<'\n';
}
<풀이 과정>
A~Z 까지 값들중 값을 0~9까지 배분할 수 있으며 알파벳의 최대 개수는 10개이고 수의 길이는 최대 8이라고 한다.
이 문제를 푸는 접근법은
TestCase:
2
AAA => 100 * A + 10 * A + 1 * A
AAA => 100 * A + 10 * A + 1 * A
총 222A가 됨을 확인할 수 있다. 비교할 알파벳이 없기 때문에 A에 9의 값을 부여하면 되므로 999 + 999 = 1998이 된다.
2
ABBCC
DDEFF
D = 11000 * 9 (가장 큰 값)
A = 10000 * 8(다음 값)
B = 1100 * 7
E = 100 * 6
C = 11 * 5
F = 11 * 4
이런 식으로 풀어 나가면 된다. 각 자리마다 (부여한 값) * 1,10,100,1000,10000...을 곱해줘야 되기 때문에 pow함수를 활용하였고, 다 더한값을 sort함수를 통해 내림차순 정렬시켰다.
마무리 단계로 num = 9부터 시작해 벡터 alpha에 값이 존재하면 그 값에 9,8,7....을 곱해줘서 최적화된 값을 구할 수 있다.
'PS > 그리디 알고리즘[Greedy]' 카테고리의 다른 글
백준 20044 Project Teams(c++) (0) | 2022.09.18 |
---|---|
백준 2170 선 긋기(c++) (0) | 2022.08.06 |
백준 1781 컵라면(c++) (0) | 2022.07.21 |
백준 1049 기타줄(c++) (0) | 2022.07.21 |
1049 기타줄(c++) (0) | 2022.07.21 |