[백준 알고리즘][백트래킹] 1339번 단어 수학

문제 정의

알파벳으로 이루어진 N개의 단어가 수학문제가 들어오면, 각 알파벳을 숫자에 대응시켜 합을 구했을 때 가장 큰 합이 나오도록 만들어야 한다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1339)

문제 풀이

숫자는 0~9 까지 각 알파벳에 대응시킬 수 있으므로, 최대 대응을 시켜야하는 수는 10개의 알파벳이다.(입력자체도 모든 단어에 포함되어 있는 알파벳이 최대 10개이다.) 두줄에 걸쳐 입력되는 알파벳숫자들의 합이 최대가 되려면 일단 제일 앞자리에 있는 알파벳에 9,8,7... 순으로 큰 수를 대응시켜주면 된다. 문제는 하나의 알파벳이 두번 입력되어도 그 알파벳은 하나의 수로 대응되어야하니까 적절하게 대응시킬 수 있는 방법이 필요하다. 해결해야되는 부분들을 하나씩 정리해봐야겠다.

1. 제일 긴 단어에서부터 숫자를 대응시켜준다.

2. 1번의 조건대로 만약 하나의 알파벳에 하나의 숫자를 대응시켰는데, 다음 단어에서 더 앞부분에 이미 대응시켜놓은 알파벳이 나타날 경우 다시 돌아가서 더 앞부분에 있는 알파벳이 큰 수를 가질 수 있도록 새로 수를 정해준다.

3. 제일 긴 단어에서부터 숫자를 대응시키되, 만약 길이가 5, 3, 2인 단어가 들어와있다면 길이가 5인 아이의 첫번째, 두번째, 세번째자리 알파벳을 대응시키고 길이가 3인 아이의 첫번째 자리를 대응시키고, 다시 길이가 5인 아이의 네번째자리를 대응시키고, 3인 아이의 두번째자리륻 대응시키고, 2인 아이의 첫번째 자리에 숫자를 대응시키도록한다. 무작정 하나의 단어에 대응을 끝내고 넘어가는게 아니라 제일 긴 길이에 해당하는 자리 알파벳부터 대응시킨다. 

4. 최소한 현재 대응시켜줘야하는 단어가 몇번째 단어인지, 해당 단어의 어느자리를 대응시킬 것인지를 알아야하니까 백트래킹 함수의 파라매터는 2개 이상이어야한다.

위의 조건들을 고려하면서 예제 입력 3개에는 다 맞게 답이 나오는 코드를 작성했다! 근데 틀렸습니다가 나오길래 질문검색을 참고했는데 입력이 2, BC, AA와 같이 들어오면 A=9, B=8, C=7을 대응시켜서 186이 나와야한다. 그렇지만 나는 저런 예외를 생각못해서 먼저 들어온 BC를 먼저 보며 B=9, A=8, C=7을 대응시켜서 185가 나온다! 같은 자리에 있는 알파벳들중에 가장 많이 사용되는 알파벳에 더 큰수를 대응시켜야한다. 나는 입력받을 때도 %s로 받아서 어떤 알파벳이 얼마나 많이 들어오는지 체크도 못하게 짰는데.. 고치기 위해서 알파벳의 빈도를 파악하고 그거에 맞춰서 단어를 정렬하면 지금 짠 함수로 해결할 수 있을 것 같다. 알파벳의 빈도순으로 문자열을 sorting 했는데도 틀렸습니다가 떠서 어디가 잘못됐는지를 모르겠다. 아까 해결하지 못했던 테스트케이스도 해결했는데 어느 부분이 잘못됐는지 감이 안오니 고칠 수가 없다. 

*여러가지 조건들을 생각날 때마다 추가하며 코드를 고쳐나갔는 데 잘 풀리지 않는다. 백트래킹을 사용하고 싶은데 개념적으로 잘 접근이 안된다. 다른 설명을 참고하고자 검색을 했는데 수학적으로 너무 쉽게 풀리는 문제였다! 일단 시작한 코드에서 백트래킹으로 해결하고 싶은데 잘 풀리지 않는다. 리뷰를 보니 어려운 문제라고 한다. 다른 백트래킹 문제를 먼저 풀고 다시 풀어봐야겠다.

+추가 2018.11.07

처음 이 문제를 풀 때는 백트래킹 관련 문제들만 보아서 풀었었던 것 같다. 이번에 다시 이 문제를 읽었을 때는 백트래킹을 써야겠다 생각은 들지않았고, 더 앞자리에 있는 수부터 매칭을 하되 빈도에 가중치를 둬서 차례대로 할당하면 되겠다 생각을 했다. 각 자리수별로 벡터에 넣어주고, 각 벡터는 빈도수에 따라 정렬한다. 그러면 제일 앞자리에 있으면서도 빈도가 가장 높은 수에 매칭을 하게 된다. 

이렇게 생각하고 어제 풀었는데 1%에서 바로 틀렸길래 다시 한번 정리해보려고 위에 3줄을 쓰면서 잘못된 점을 찾았다. 나는 단순히 빈도수만 사용했기 때문에 만약에 ABCC BCCA 와 같이 나타나면 A, B 둘 다 두번나타나니까 가중치가 똑같다. 하지만 첫번째 자리에 있는 A, B 중에 더 큰애를 할당해줘야하는 건 B다! A는 두번째에서 네번째자리에서 나타나고 B는 두번째 자리에서 나타나니까 B가 더 높은 수를 할당받아야 된다! 다들 이 부분을 고쳐주려고 바로 1000, 100 와 같은 수로 가중치를 할당해줬던 거구나.. 같은 방법으로 풀거나 지금의 내 코드에서 저 방법을 적용시키도록 해야겠다.

내가 생각했던 방법에서 이미 잘못된 부분이 있었다. 더 앞자리의 수에 무조건 더 큰 애를 할당해줘야한다 생각했는데 가중치에 따라 달라지는 것 같다. 결국 간단히 하면 다들 수학적으로 푼 코드와 같아진다. input 범위조정에 있어서 문제가 있어서 계속 틀렸습니다를 받았었다. 해결!

코드

#include<iostream>

#include<string>

#include<algorithm>

#include<math.h>

#include<functional>

#include<queue>

using namespace std;

int N;

int check[26];

int main(){

string input;

priority_queue<int> weight;

cin>>N;

for(int i=0; i<N; i++){

cin>>input;

for(int j=0; j <input.size(); j++){

check[input[j]-'A'] += pow(10.0, double(input.size()-1-j));

}

}

for(int i=0; i<26; i++)

weight.push(check[i]);

int alloc = 9, result=0;

while(!weight.empty()){

result += weight.top()*alloc--;

weight.pop();

if(alloc == 0)

break;

}

cout<<result<<endl;

return 0;

}