백준 1339 - 단어 수학

1. 첫번째 아이디어는 가장 긴 문자열의 앞 숫자가 가장 크면 모두 더한 값이 가장 크지 않을까 라는 생각으로 바로 코드를 작성하였다

결론부터 말하자면

ABB

BB

BB

BB

BB

BB

BB

일 경우 내코드를 988 + 88 + 88 + 88 + 88 + 88인데 더 큰 값은 899 + 99 + 99 + 99 + 99 + 99인 경우로 내 이론에 오류가 있었다

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>

#define Fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

typedef long long ll;  



int main() {
    Fast;

    int n;
    short length[10] = { 0, };
    string strs[10];
    bool visited[10] = { false, };
    short resultArr[26] = { 0, };
    short curMaxLength = 0;

    cin >> n;

    short iter = 0;
    for (int i = 0; i < n; i++) {
		cin >> strs[i];
		length[i] = strs[i].length();
        curMaxLength = max(curMaxLength, length[i]);
        iter += length[i];
	}

    short curNum = 9;
    while (iter > 0) {
        for (int i = 0; i < n; i++) {
            if (length[i] == curMaxLength) {
                char c = strs[i][strs[i].length() - curMaxLength];
                char checkIndex = c - 65;
                if (!visited[checkIndex]) {
					visited[checkIndex] = true;
                    resultArr[checkIndex] = curNum;
                    curNum--;

				}
                length[i]--;
                iter--;
			}
		}
		curMaxLength--;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < strs[i].length(); j++) {
            char c = strs[i][j];
            strs[i][j] = resultArr[c - 65] + '0';
		}
	}


    ll result = 0;
    for (int i = 0; i < n; i++) {
		result += stoll(strs[i]);
    }

    cout << result;

    return 0;
}

 

2. 오류를 깨닳았고 이번에는 그리드 방식으로 되는대로 전부다 순회해 가며 값을 체크해 보려고 한다

예를 들어 A B C D E라는 문자에 0 ~ 9 까지 하나 하나 대입해 보면서 값을 계산하는 것이다

 

결과는 성공했지만 안타깝게도 역시 많은 시간이 걸리게 되었다

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>

#define Fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

typedef long long ll;  

int n;
vector<string> arr;
map<char, int> m;
vector<bool> visited(10, false);
ll max_result = 0;

ll check() {
    ll result = 0;
    for (int i = 0; i < n; ++i) {
        int cnt = 1;
        for (int j = arr[i].size() - 1; j >= 0; --j) {
            result += m[arr[i][j]] * cnt;
			cnt *= 10;
		}
	}
    return result;
}

void sol(int iter, map<char, int>::iterator iters) {
    if (iter == m.size()) {
        max_result = max(max_result, check());
        return;
    }

    for (int i = 0; i < 10; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        m[iters->first] = i;
        iters++;
        sol(iter + 1, iters);
        iters--;
        visited[i] = false;
	}
}


int main() {
    Fast;

    cin >> n;
    arr.resize(n);

    for (int i = 0; i < n;++i) {
        cin >> arr[i];
        for (auto c : arr[i]) {
            m[c] = 1;
		}
    }

    sol(0, m.begin());
    cout << max_result << '\n';
    return 0;
}

 

3. 다시 한번 곰곰히 생각해보니 각각의 문자의 위치가 이미 정해져 있다는 것을 확인하여서 이를이용해 다시한번 풀어봐야겠다