[BOJ] 1339 : 단어 수학

1339 : 단어 수학

풀이

그리디

원래는 백트래킹으로 순열을 써서 풀었다. 그런데 예제케이스의 10 ABCDEFGHI 이부분이

제출했을때는 500ms로 통과되는데, 로컬에서는 10초정도가 걸린다. 찝찝하다.

질문게시판에 보니까 그리디로도 풀린다고 한다. 그래서 곰곰이 생각해보니까

각 알파벳의 위치에 따라 가중치를 더한다음 큰순서대로 9,8,7…값을 할당받아서

곱한값을 출력하면 되는것이다.

계산을 편하게 하기위해 입력 string을 reverse한 뒤

해당 알파벳의 위치에 따라 가중치를 곱해서 vector에 넣어준다.

그후에 큰숫자가 앞으로오게 sort하고, 큰순서대로 9,8,7,6,5,4,3,2,1,0 값을 곱해주면 끝.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <functional>
using namespace std;
vector<int> v(26);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        reverse(tmp.begin(), tmp.end());
        int ten = 1;
        for (int i = 0; i < tmp.size(); i++) {
            v[tmp[i] - 'A'] += ten;
            ten *= 10;
        }
    }
    sort(v.begin(), v.end(), greater<int>());
    int ans = 0;
    int num = 9;
    for (auto x: v) {
        ans += x*num;
        num--;
    }
    cout << ans;
    return 0;
}

Written on April 7, 2019