백준 1339 단어 수학

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

1339번: 단어 수학

알파벳에 1부터 10까지 숫자를 부여해서 주어진 식의 합이 최대가 되는 것을 출력하는 것으로 

어떻게 보든 모든것을 완전 탐색을 해봐야 아는 문제입니다.

A 에도 1 부터 10까지

B 에도 C에도 Z까지 각 1부터 10까지 부여해야 하므로 가장 간단한 완전 탐색 방법 중 하나인 재귀를 이용한 백트래킹을

사용하면 됩니다.

 

기본 모든 순열을 찾아서 각 알파벳에 주어진 숫자를 정수로 바꾸어 나온 결과에 최댓값만 뽑아내면 됨으로 

설명은 여기까지 맞추고 소스를 보고 이해하시기 바랍니다.

처음에 실수했던 것은 모든 예제가 잘 나왔었는데 우연히 예제가 맞았던 것 같고

사용된 알파벳을 체크하는 Alpha 배열은 제대로 했는데

그 Alpha에 저장된 사용된 알파벳의 순서를 넣어놓은 구조체 배열에 조금 오류가 생겨 좀 난감했던 문제였습니다.

 

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char input[11][11];
int N;
int Alpha[26];
bool cmp(int a, int b)
{
    return a > b;
}
typedef struct Data {
    int num;
}D;
D Alpha1[26];
int idx = 0;
int ten[11] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,1000000000 };
void init() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%s", input[i]);
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < strlen(input[i]); j++)
            Alpha[input[i][j] - 'A'] = 1;
    }
    for (int i = 0; i < 26; i++) {
        if (Alpha[i] == 1) {
            Alpha1[i].num = idx++;
        }
    }
    //sort(Alpha, Alpha + 24,cmp);
}
int num[26];
int chk[26];
long long int Max = -987654321;
void dfs(int id) {
 
    if (id == idx) {
        long long int ret = 0;
 
        for (int i = 0; i < N; i++) {
            int len = strlen(input[i]);
        int ten1 = len - 1;
        
            for (int j = 0; j < len; j++)
            {
 
                ret += num[Alpha1[input[i][j] - 'A'].num] * ten[ten1--];
            }
        }
        if (Max < ret) Max = ret;
        return;
    }
    else {
        for (int i = 9; i >= 9 - idx + 1; i--) {
            if (num[id] == -1 && chk[i] == 0) {
                chk[i] = 1;
                num[id] = i;
                dfs(id + 1);
                num[id] = -1;
                chk[i] = 0;
            }
        }
    }
}
int main(void) {
 
    init();
    for (int i = 0; i < 26; i++) {
        num[i] = -1;
    }
    dfs(0);
    printf("%lld", Max);
    return 0;
}

주어진 각각의 숫자를 하나의 정수로 만드는 방식은 여러 가지지만 저는 배열에 10의 배수를 넣고 인덱스로

가져다 쓰는 방식을 사용했습니다.

오늘은 여기까지이고 질문이나 이상한 점 있으시면 태클 부탁드립니다.