BOJ 1339 : 단어수학

풀이 요약

수학 문제

풀이 상세

1. 알파벳을 $N$ 의 자리가 크면서, 갯수가 많은 수로 정렬 한다.

2. 예를 들어 $AAA$, $BABB$ 라면 $A$ 는 $(2*100)+(1*10)+(1*1) = 211$, $B$ 는 $(1*1000)+(1*10)+(1*1) = 1011$ 이 된다. 따라서 $B$ 가 최댓값인 $9$ 가 되며, $A$ 는 그 다음값이 된다.

3. 위의 식을 기반으로 구현하면 답이 나온다.

배운점

• for문에서 혹은 sort() 에서 마지막 인덱스를 나타내기 위한 용도로, sizeof(arr), arr.length() 를 썼는데 본래 길이인 10이 아닌 다른 값(240)이 나오더라. 왜그런걸까

#include <iostream>
#include <algorithm>
using namespace std;
const int arr_LEN = 10;
const int A_LEN = 26;
int N, A[A_LEN];
string arr[arr_LEN];

bool cmp(int n1, int n2) {
    return n1 > n2;
}

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    for (int i = 0; i < N; i++) {
        int idx = 1;
        for (int j = arr[i].length() - 1; j >= 0; j--) {
            A[arr[i][j] - 'A'] += idx;
            idx *= 10;
        };
    }

    sort(A, A + A_LEN, cmp);
}

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

void output(int ans) {
    cout << ans;
}

int main() {
    input();
    int ans = solve();
    output(ans);
}