[백준] 1132번 합 (C++)

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

 

 

이 문제는 N개의 수가 주어지고 N개의 알파벳이 주어질때 각 알파벳에 0부터 9까지 사상시켜 최댓값을 만들어야 하는 문제이다.

 

처음엔 모든 경우의 수를 다 찾는 방법밖에는 없다고 생각하여 주어진 알파벳들을 백트래킹을 사용하여 다 탐색하여 최댓값을 리턴하는 방식을 사용했지만 N이 최대 50이며 알파벳이 10개가 입력된다고 가정했을때 

 

시간복잡도는 O(10! * N)으로 1억을 가뿐히 넘긴다.

 

따라서 다른 방법으로 접근해야 하는데 결국 알파벳의 각 자리수가 존재하기 때문에 이를 이용해서 그리디하게 풀어보았다.

 

먼저 첫번째 테케 ABC, BCA의 예시를 보자

A는 100의 자리 1의 자리가 존재하여 총 101이다 B는 10의 자리 100의 자리가 존재하여 110이다 마지막으로 C는 1의 자리 10의 자리가 존재하여 11이므로 이 값들을 정렬했을때 110, 101, 10이 된다. 즉 B의 값에 가장 큰 9, 이후 A의 값에 8, C의 값에 7을 넣으면 가장 큰 숫자를 얻을 수 있는걸 알 수 있다.

 

따라서 각 알파벳의 값이 모두 존재하는 경우 이는 0을 넣을 가장 작은 곳을 찾아야하기 때문에 가장 작은 것의 인덱스를 찾아 0으로 만들어 정렬후 순차적으로 9부터 1까지 값을 곱하여 더해주었다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e13

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N;
int64_t alpha[10];
bool zero[10];

void Print() {
    for(int i = 0; i < 10; i++) {
        cout << alpha[i] << " ";
    }
    cout << endl;

    for(int i = 0; i < 10; i++) {
        cout << zero[i] << " ";
    }
    cout << endl;
}

void solve() {
    bool flag = false;
    for(int i = 0; i < 10; i++) {
        if(!alpha[i]) {
            flag = true;
        }
    }

    if(!flag) {     //      이미 알파벳이 다 채워져 0을 
        int64_t tmp = MAX;
        int idx = 0;

        for(int i = 0; i < 10; i++) {
            if(!zero[i] && tmp > alpha[i]) {
                tmp = alpha[i];
                idx = i;
            }
        }
        alpha[idx] = 0;
    }

    sort(alpha, alpha+10, [&](int64_t a, int64_t b) {
        return a > b;
    });

    int64_t answer = 0;
    for(int i = 0, j = 9; i < 10; i++, j--) {
        answer += alpha[i] * j;
    }

    cout << answer;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        int64_t cnt = 1;
        string s;

        cin >> s;

        zero[s[0] - 'A'] = 1;

        for(int j = s.size()-1; j >= 0; j--) {
            int idx = s[j] - 'A';
            alpha[idx] += cnt;
            cnt *= 10;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}