BOJ 1339 단어 수학

1339번: 단어 수학

 

단어들의 합이 최대가 되어야 한다는 점 때문에 자칫 착각할 수 있지만, 문제 자체는 각 단어들에서 가장 많이 등장한 알파벳부터 9, 8, 7, ... 0 의 가중치를 주기만 하면 되는 간단한 문제이다.

 

하나의 단어에 대하여 문제를 풀 수 있다면 여러 개의 단어를 대상으로도 같은 해법으로 접근이 가능하다.

 

---

 

위와 같이, 단어 테이블과 알파벳 테이블을 이용하여 단어 한 개에 대하여 문제를 해결한 뒤, 여러 개의 단어에 상황에 적용해보자

---

 

아이디어를 간단하게 정리할 수만 있다면 규칙(= 알고리즘) 이 굳이 필요 없을 정도로 간단한 문제므로 우선 [ABCEFG] 단어에 대하여 문제를 해결해보자.

 

 

ABCEFG는 위와 같이 분해될 수 있다. 이 단어 테이블을 이용해 알파벳 테이블에 등장한 횟수를 저장하면 된다.

이때 주의할 점은 6자리 단어 [A ? ? ? ? ?] 는 A가 1번 등장한 것이 아니라 100000번 등장한 것으로 생각해야 한다는 점이다.

 

 

 

즉 위와 같이 알파벳 테이블을 만들어 주어야 한다.

그 뒤, 알파벳 테이블에서 값이 큰 문자부터 9, 8, 7, ... 0 의 숫자를 할당한다.

 

 

 

 

이상의 방법으로 문자 하나에 대한 가장 큰 숫자를 만들 수 있다. 이를 문제의 예시 GCF + ACDEB에 적용하여 수행해보자.

 

 

 

 

 

 

 

 

 

여기서 B와 F의 등장 횟수가 동일하지만 이는 어떤 값에 3이 들어가도 결과는 동일하다

 

 

 

 

 

---

 

 

 

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지