백준 1339번 단어 수학 (C++)

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

1339번: 단어 수학

 

 

------------- 접근법

처음 보면 Backtracking 인가? 

 

최적의 해를 어떻게 구할 수 있지? 라는 고민을 먼저 하게 된다. 

PS를 하면서 느끼는 건 "이렇게 하면 답이 나오는데 증명이 안됐다" 라는 해는 사용하면 안된다 맞는 경우도 있겠지만 매우 위험하다.

 

이 문제도 마찬가지다.

ABCDE

     FCG 에서 AB까지는 9 8 을 하고 나머지는 번갈아가며 7 6 5 4.. 를 주니 답이나오는 것 같았다. 그러나 증명이 안됐다. 그렇다면 정답이 아니라고 봐야한다.

 

여기서는 수학적 통찰력이 관건이 된 문제였다. 난 물론 찾아내지 못했다. ABCDE 와 FCG는 사실 다음과 같다.

A * 10000

B * 1000

C * 100

D * 10

E * 1

 

+

 

F * 100

C * 10

G

 

종합해보면 

 

A * 10000

B * 1000

C * 110

D * 10

E * 1

F * 100

G * 1 

 

이므로 제일 큰 수 부터 9~ 할당하면 된다. 이게 왜 그리디인지는 잘 모르겠다. 오히려 수학과 센스, 통찰력이 더 중요한 문제라고 생각한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<string> words;

int squar(int n) {
	int result = 1;
	for (int i = 0; i < n; i++) {
		result *= 10;
	}

	return result;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;
	map<char, int> mapping;

	for (int i = 0; i < N; i++) {
		string word;
		cin >> word;

		for (int i = 0; i < word.size(); i++) {
			if (mapping.find(word[i]) == mapping.end()) { // 찾지 못함 
				mapping.insert({ word[i], squar(word.size() - i - 1) });
			}
			else {
				mapping[word[i]] += squar(word.size() - i - 1);
			}
		}
	}

	vector<int> vec;

	for (auto a : mapping) {
		vec.push_back(a.second);
	}

	sort(vec.rbegin(), vec.rend());
	int answer = 0;
	for (int i = 0; i < vec.size(); i++)
		answer += vec[i] * (9 - i);

	cout << answer << '\n';
}