[백준 1339번] 단어 수학

난이도: 골드 4

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

1339번: 단어 수학

문제 1339번: 단어 수학

백준에서 본 문제는 그리디 알고리즘, 브루트포스 알고리즘, 백트래킹 문제로 분류하고 있습니다.

 

이 중 백트래킹 문제는 제가 무슨 의미인지 잘 모르기 때문에 (...),

분류 자체를 너무 신경쓰지 않고 풀기로 했습니다.

 

알파벳 26개 중 최대 10개에, 0~9까지의 값어치를 부여하고,

알파벳을 숫자로 간주하여 계산했을 때의 최댓값을 구하는 문제입니다.

 

제 접근법은 이러합니다:

1. vector<pair <int, string> >을 사용하여, 입력된 단어와 그 단어의 길이를 쌍으로 저장한다.
2. 입력이 완료되면, 단어의 길이를 중심으로 vector를 sort한다.
3. 별도의 크기 26의 int형 array에, 각 문자별 weight를 합산하여 저장한다. (1의 자리 1, 10의 자리 10, ...)
4. weight를 저장한 array를, weight가 높은 순서대로 sort한다.
5. 이후 각 weight에 걸맞는 값을 곱하여 answer를 구한다.

다행히 제 발상이 정답에 가까웠나 봅니다.

더 간단히, STL을 덜 쓰고 문제를 풀 수 있지 않았을까 싶긴 하지만, 그런대로 잘 풀린 것 같아서 만족합니다.

5번에서 약간 어려움을 겪었는데, 각 문자별 weight를 자릿수에 맞춰 대입하고 (예: 100의 자리 숫자의 weight는 100),

weight에 우선순위를 9부터 차례로 곱해서 합산하니 쉽게 답이 나왔습니다.

 

요약하면,

모든 단어를 다 확인하여, 각 단어의 알파벳을 확인하고, 알파벳에 숫자의 자릿수에 해당하는 값을 기록합니다.

이후, 합산된 값에 (예: A = 11020) 우선순위를 곱해서 합산하면 원하는 결과를 얻을 수 있습니다.