백준 1339 - 단어 수학
Updated:
C++
1339번 - 부등호
문제
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.
단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.
N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 문제 출처
접근 방법
완전 탐색이지만 Greedy로 생각하면 더 효율적이게 해결이 가능하다.
예제 입력 2를 사용하여 설명하면,
GCF는 100G + 10C + F 이며
ACDEB는 10000A + 1000C + 100D +10E + B 이다.
두개를 더하면 10000A, 1010C, 100G, 100D, 10C, F, B 가 되며, 큰 수부터 9~1을 배정하여 계산한다.
구현
alpha는 각 알파벳 자리를 뜻한다 따라서 26만큼의 크기로 배정하였다.
0은 A이고 1은 B…. 25는 Z 이런식으로 배정한다.
alpha[temp[j] - 'A'] 문자에 ‘A’ 만큼을 차감하면 아스키 코드로 인해 A~Z는 0~25로 각각 매핑이 된다.
sort를 통해 정렬하여 각 알파벳의 수가 큰 수를 정렬하고, 앞에서 부터 9~1을 배정하여 단어의 합을 계산한다.
코드 - Back Tracking
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
int n;
long long result;
long long alpha[26];
bool comp(int a, int b) { //오름차순을 위한 조건
return a > b;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
string temp;
for (int i = 0; i < n; i++) {
cin >> temp;
for (int j = 0; j < temp.size(); j++) {
alpha[temp[j] - 'A'] += pow(10, temp.size() - j - 1);
}
}
sort(alpha, alpha + 26, comp);
int idx = 9;
for (int i = 0; i < 26; i++) {
if (alpha[i] == 0)
break;
result += alpha[i] * idx;
idx--;
}
cout << result;
return 0;
}
