[BOJ/1339] 단어 수학, c++

www.acmicpc.net/problem/1339

1339번: 단어 수학

github.com/jokj624/PS/blob/master/1000-5000/1339.cpp

jokj624/PS

 한줄 후기 : 그냥 숫자로 더하세요 제발..

 

주어진 알파벳에 숫자를 부여하여 더할 때, 최댓값이 나오도록 해야하는 문제이다.

1회 WA 받고 2회때 맞췄다.

처음에 생각한 방법은 그리디 하게 접근하는데 문자열 길이가 가장 긴 애들순서로 정렬을 시키고 가장 자릿수가 큰 수부터 9부터 부여하는 대신 

ACDEB

    GCF 일때, AC 까지 9-8을 부여한다. 즉 바로 뒤에 있는 문자열길이와의 차 (5-3) 만큼만 부여하고 뒤로 넘어간다.

그 이후 부터는 나머지 자릿수들에 차례대로 남은 수들을 부여하도록 구현했다.

//WA
//BOJ 1339 단어 수학
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
vector<string> v;
int arr[27];
bool cmp(const string &a, const string &b){
	return a.size() > b.size();
}
int main(){
	int n, num = 9;
	cin >> n;
	for(int i=0; i<n; i++){
		string s;
		cin >> s;
		v.push_back(s);
	}
	sort(v.begin(), v.end(), cmp);
	fill(arr, arr+27, -1);
	for(int i=0; i<n; i++){
		if(i == n-1){
			if(arr[v[i][0]-'A'] == -1){
				arr[v[i][0]-'A'] = num;
				num -= 1;
			}
			break;
		}
		int d = v[i].size() - v[i+1].size();
		for(int j=0; j<d; j++){
			if(arr[v[i][j]-'A'] == -1){
				arr[v[i][j]-'A'] = num;
				num -= 1;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<v[i].size(); j++){
			if(arr[v[i][j]-'A'] == -1){
				arr[v[i][j]-'A'] = num;
				num -= 1;
			}
		}
	}
	long long N = 0, sum = 0;
	for(int i=0; i<n; i++){
		N = 0;
		for(int j=0; j<v[i].size(); j++){
			N += (arr[v[i][j]-'A'] * pow(10, v[i].size()-(j+1)));
	//		cout << N << endl;
		}
		sum += N;
	}
	cout << sum;
	return 0;
}

 

 

 

이런 식으로 구현했다. 틀렸다!

반례는 (나처럼 틀린 사람이 많았나 보다........)

10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB
정답값 : 1790
출력값 : 1780

이다.

즉, 자릿수가 중요한게 아니라 '자릿수의 합'이 중요한 문제다.

전체 자릿수의 합이 큰 알파벳부터 9를 부여하면 된다.

A의 자릿수 합은 100, B의 자릿수 합은 110 이라 B에 9를 부여하고 A에 8을 부여해야 정답이다.

 

//AC
//BOJ 1339 단어 수학
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
using namespace std;
vector<string> v;
map<int, int> m;
int arr[27];
bool cmp(const pair<int,int>& a, const pair<int,int>& b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second > b.second;
}
int main(){
	int n, num = 9;
	cin >> n;
	for(int i=0; i<n; i++){
		string s;
		cin >> s;
		v.push_back(s);
	}
	long long N = 0, sum = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<v[i].size(); j++){
			m[v[i][j]-'A'] += pow(10, v[i].size()-(j+1));
		}
	}
	vector<pair<int,int>> vec( m.begin(), m.end() );
	sort(vec.begin(), vec.end(), cmp);
	for(int i=0; i<vec.size(); i++){
		arr[vec[i].first] = num;
		num -= 1;
	}
	for(int i=0; i<n; i++){
		N = 0;
		for(int j=0; j<v[i].size(); j++){
			N += (arr[v[i][j]-'A'] * pow(10, v[i].size()-(j+1)));
		}
		sum += N;
	}	
	cout << sum;
	return 0;
}

map을 이용해 구현했다.

map[key(알파벳) index] = 자릿수의합

으로 저장해놓고, 정렬을 통해 자릿수의 합이 큰 알파벳부터 정렬해줬다.

정렬 후, 자릿수의 합이 가장 큰 알파벳 위치부터 9를 부여해주면 된다.