[백준 1339] 단어 수학

문제 출처: https://www.acmicpc.net/problem/1339

풀이

백트래킹으로 분류된 문제지만 이렇게풀어도될 것 같은데? 해보니 풀린 문제입니다. 

문자열 S를 앞에서부터 10의 제곱꼴로 저장해놓고 9,8,7,6...순으로 곱하면서 최댓값을 구할 수 있습니다. 아래에 문제 풀이 순서대로 적어보았습니다.

1. int형 알파벳 배열 선언하기

알파벳 갯수를체크하기위함이 아닌 입력받은S의 첫번째 알파벳부터 10의 제곱꼴로 하여 저장하기위해 선언. n번 만큼 반복해서 값을 누적시킵니다.

2. 최댓값을 구하기위해 알파벳 배열에 담긴 값들을 큰값부터 정렬시키기

3. 정렬시킨 알파벳배열의 값들이 최댓값 순으로 정렬되어있으므로 각 값들을 9,8,7,6...순으로 곱해나가기. 결국 최종sum이 최댓값이 되어있음

코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int alpa[26], n;
vector<int>v;
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin >> n;
    string s;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        for (int i = 0; i < s.size(); i++)
        {
            //입력받은 알파벳들 제곱꼴로 값 저장
            alpa[s[i] - 'A'] += pow(10, s.size() - i - 1);
        }
    }
    sort(alpa, alpa + 26, greater<int>());
    int key = 9, sum = 0;
    for (int i = 0; i < 26; i++)
    {
        if (alpa[i])
        {
            sum += alpa[i] * key;
            key--;
        }
    }
    cout << sum << '\n';
}

결과