[Beakjoon] 1132 합 (C++)

문제 링크

BOJ 1132 : 합

문제

N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 시작하는 수는 없다. 이때, 가능한 수의 합 중 최댓값을 구해보자.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 수가 주어진다. 수의 길이는 최대 12이다. 적어도 한 알파벳은 수의 가장 처음에 주어지지 않는다.

출력

첫째 줄에 합의 최댓값을 출력한다.

풀이

합을 최대로 만들기 위해 특정 알파벳이 의미하는 수를 결정하는 문제이다.

합이 커지기 위해서는 높은 자리수에 위치한 알파벳이 큰 수를 가져야 한다. 이를 위해 각 알파벳마다 위치한 자리수에 따라 점수를 부여하고 정렬하여 높은 순위에 위치한 알파벳부터 높은 수를 부여하는 것이 아이디어이다.

여기서 예외가 되는 것은 0으로 시작하는 수가 없다는 것이다. 즉 주어진 알파벳 문자열들에서 가장 앞에 위치한 적이 있는 알파벳은 0을 부여하면 안된다.

맨 앞에 위치한 적이 없는 알파벳들 중 가장 우선순위가 작은 알파벳에 0을 부여한다.

나는 이를 구현하기 위해 정렬을 한 번 하고 맨 끝에 존재하는 알파벳을 제외하고 모두 맨 앞에 존재한 적이 있다고 가정하도록 값을 업데이트 해주는 방법을 선택했다.

이렇게 바꿔준 후 다시 한 번 정렬하면 의도한대로 정렬이 된다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

#define endl "\n"

using namespace std;

int N;
pair<int,long long> A[11];

bool compare(pair<int,long long> a, pair<int,long long> b){
    if(a.first == b.first) return a.second >= b.second;
    else return a.first >= b.first;
}
void Solve() {
    cin>>N;
    string s;

    for(int i=0; i<N; i++){
        cin>>s;
        A[s[0]-'A'].first = 1;
        for(int j=0; j<s.size(); j++){
            A[s[j]-'A'].second+=pow(10,s.size()-j-1);
        }
    }
    
    long long sum=0;
    sort(A, A+10, compare);
    for(int i=0; i<9; i++) A[i].first = 1;
    sort(A, A+10, compare);

    for(int i=0; i<10; i++){
        sum+= A[i].second*(9-i);
    }

    cout<<sum;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}