백준 1339번 단어 수학

🔒[문제 url]

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

🔑알고리즘

단어를 알파벳이 아닌 숫자로 보아야한다.

• 2 ABC BCA가 입력으로 주어진 경우
  • 두 단어를 따로 생각해보면,
    ABC = 100A + 10B + 1C , BCA = 100B + 10C + 1A 가 된다.
    따라서 두 수의 합은 101A + 110B + 11C 이므로,
    가장 크기가 큰 순서인 B C A 순으로 9 8 7 을 각각에 할당한다.
    
    

1. cnt 배열을 설정해 각 알파벳의 크기를 측정한다.
2. 가장 크키가 큰 알파벳부터 큰 수를 배정하기위해, cnt를 내림차순으로 정렬한다.
3. cnt를 순회하며 9부터 1씩 감소하며 차례대로 배정하고, 크기와 배정된 수의 곱을 출력할 답안 ans에 더해준다.

🐾부분 코드

for (int i = 0; i < n; i++)
    for (int j = 0; j < str[i].length(); j++) // Be careful with the idx
        cnt[str[i][j] - 'A'] += pow(10, str[i].length() - 1 - j);

<알파벳 크기 측정>
모든 단어에 대해 각 알파벳의 크기를 구한다.
j번째 자릿수의 경우, 크기는 $10^{str[i].length() - 1 - j}$ 가 된다.

이후, 알고리즘에 따라 크기를 내림차순 정렬 후 큰 수부터 곱하며 답에 더해간다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
string str[10];
int cnt[26];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> str[i];
}

bool comp(int a, int b)
{// Sort descending
    return a > b;
}

void SOLVE()
{
    /* Example
    *  Input : 2 ABC BCA
    * 
    *  Answer is biggiest (100A + 10B + 1C) + (100B + 10C + 1A)
    *                       = 110B + 101A + 11C
    *  So, assing 9 to B, 8 to A, 7 to C
    * 
    *  Output : 1805
    */

    // So, Count It!!
    for (int i = 0; i < n; i++)
        for (int j = 0; j < str[i].length(); j++) // Be careful with the idx
            cnt[str[i][j] - 'A'] += pow(10, str[i].length() - 1 - j);

    //Sort Descending to assign in descending order
    sort(cnt, cnt + 26, comp);

    int ans = 0, value = 9;
    for (int i = 0; cnt[i] != 0; i++)
    {
        ans += cnt[i] * value;
        value--;
    }
    cout << ans;
}


int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

Greedy는 늘 수학적 사고가 요구되는 듯 하다.
수학 태그도 틈틈이 풀어야지..!
알고리즘만 떠올렸다면 코드 구현은 실버 하위급인듯 하다.
그치만? 나는 알고리즘을 한참동안 헤맸다는 것!