[백준] 1339-단어 수학(C++)

문제링크: https://www.acmicpc.net/problem/1339

1339번: 단어 수학

 

간만에 풀어보는 그리디 알고리즘!

 

접근방식

 

1. 일반적인 접근방식으로 숫자 자릿수가 큰 경우에 높은 숫자를 배정해주면 될거라고 생각함

 

ex) accc + bbb일때,

a가 9가 되어야 하지요!

 

2.  다만 자릿수가 동일한 경우에 우선순위 배정을 신경써주야 한다!

 

ex) abbb + acdd

이때, a =9 는 당연하고 c와 b 중에서 b에 8을 배정해야 하는 부분!

이부분을 처리하기 위해서, 각 자릿수를 더해주는 형식으로 진행했다.

 

a = 1000 + 1000 = 2000b = 111 c = 100d = 22

 

숫자가 더 큰 친구가 높은 우선순위에 속하도록 구현하면 끝!~

 

 

문제풀이 

 

1.  문제 접근 2번에 설명한 것처럼 구현을 진행함

이때, 내림차순으로 정렬을 진행해두어야 함

 

2. 정렬된 값들을 순서대로 탐색하며 수를 배정해줌으로서 문제 해결

 

 

정답코드입니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int arr[26] = { 0, };
int n = 0;
int result = 0;

bool cmp(int& a, int& b) {
	if (a > b)
		return true;
	else
		return false;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;

		int cnt = 1;
		for (int j = temp.size() - 1; j >= 0; j--) {
			arr[temp[j] - 'A'] += cnt;

			cnt *= 10;
		}
	}

	sort(arr, arr + 26, cmp);
	int cnt = 9;
	for (int i = 0; i < 26; i++) {
		if (arr[i] == 0)
			break;

		result += arr[i] * cnt;
		cnt--;
	}

	cout << result << endl;

	return 0;
}