[BOJ/백준] 1339 단어 수학

● [문제번호 1339] 단어 수학

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

1339번: 단어 수학

 

● 알아야 할 것

: 브루트 포스 (Brute Force)

 

 

● 풀이 과정

: 브루트 포스라는 생각에 하나하나 찾아가는 걸 생각하며 구현하다보니

지저분해지고 이렇게 하는게 아닌거 같다는 생각에

구글링을 해서 풀이를 보니 경외로웠다.

 

: 문제에 입각하여 최대합을 만들어주는 방법을 생각하면

다음과 같았다.

 

1. 각 단어의 각 알파벳에 자릿값을 누적하여 기록한다.

ex) GCF

→ alphabet['G' - 'A'] = 100

→ alphabet['C' - 'A'] = 10

→ alphabet['F' - 'A'] = 1

 

2. 그 누적한 알파벳의 자릿값을 내림차순으로 정렬한다.

 

3. 맨 앞부터 9, 8, 7, 6.. 순서대로 가중치를 곱하며 총 합을 구한다.

 

예제 입력 2의 풀이과정

 

 

● 주의 할 것

: NULL

 

 

● 참고 할 것

: 풀이과정 참고

https://yabmoons.tistory.com/132

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// word : 입력받은 단어들
// alphabet : 각 알파벳에 해당하는 자릿수(?)
string word[10];
int alphabet[26];
int N;

// 각 알파벳을 자릿수로 변환
void change(int index)
{
    int weight = 1;
    for(int col = word[index].length() - 1; 0 <= col; col--)
    {
        alphabet[word[index][col] - 'A'] += weight;
        weight *= 10;
    }
}

// 변환 및 내림차순 정렬 후 자릿수에 가중치 곱하기
void calculate()
{
    // total : 단어 수학의 최대합
    // index : alphabet의 index
    // weight : 각 alphabet의 가중치
    int total = 0;
    int index = 0;
    int weight = 9;
    
    // 등장한 알파벳인 경우만
    while(alphabet[index] != 0 && index < 26)
    {
        total += (alphabet[index] * weight);
        index++;
        weight--;
    }
    
    // 정답 출력
    cout << total;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 단어 입력
    for(int n = 0; n < N; n++)
        cin >> word[n];
    
    // 단어의 각 알파벳을 자릿수로 변환
    for(int n = 0; n < N; n++)
        change(n);
    
    // 자릿수를 내림차순으로 정렬
    sort(&alphabet[0], &alphabet[26], greater<>());
    
    // 가중치 곱해서 정답 출력
    calculate();
    
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [521 - 브루트 포스 - 순열 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	2529	부등호	https://pirateturtle.tistory.com/294
2	1339	단어 수학	https://pirateturtle.tistory.com/295
3	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/296
4	14889	스타트와 링크	https://pirateturtle.tistory.com/297