백준 13339 단어수학

순열을 사용하면 시간초과가 뜬다.

 

순열 코드

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>

using namespace std;

char word[12][12];
vector<char> alphabet;
vector<int> permut_num;
int visited[12];
int output[12];
int n=0;
int max_result = 0;
int pow_num = 1;

void perm(int idx) {
    //printf("idx : %d \n", idx);
    if(idx == permut_num.size()) {
/*
        printf("~~~~~~~~~~~~~~~~~~~~ \n");
        for(int i=0;i<permut_num.size();i++) {
            printf("%d ", output[i]);
        }
        printf("\n");
*/
        int result = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<strlen(word[i]); j++) {
                int multip = strlen(word[i]);
                int muti_num = multip-j-1;

                for(int k=0; k<alphabet.size(); k++) {

                    if(word[i][j] == alphabet[k]) {
                        //printf("word[i][j] : %c \n", word[i][j]);

                        //printf("alphabet[k] : %c \n", alphabet[k]);
                        //printf("muti_num : %d \n", muti_num);
                        for(int i=1; i<=muti_num; i++) {
                            pow_num *= 10;
                        }
                        result += output[k]*pow_num;
                        pow_num = 1;

                        //printf("multip : %d \n", multip);
                        //printf("output[k] : %d \n", output[k]);
                        //printf("pow_num : %d\ n", pow_num);
                        //printf("result : %d \n", result);
                        //printf("\n");

                    }
                }
            }
        }

        //printf("result : %d \n", result);
        max_result = max(max_result, result);


        return;
    }
    for(int i=0; i<permut_num.size(); i++) {
        if(visited[i] == 0) {
            visited[i] = 1;
            output[idx] = permut_num[i];
            perm(idx+1);
            visited[i] = 0;
        }
    }
}
int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%s", &word[i]);
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<strlen(word[i]); j++) {
            alphabet.push_back(word[i][j]);
        }
    }
    sort(alphabet.begin(), alphabet.end());
    alphabet.erase(unique(alphabet.begin(), alphabet.end()), alphabet.end());

    for(int i =0; i<alphabet.size(); i++) {
        permut_num.push_back(9-i);
    }
    perm(0);




    /*
    for(int i=0; i<alphabet.size(); i++) {
        printf("%c", alphabet[i]);
    }
*/

/*
    for(int i=0; i<n; i++) {
        for(int j=0; j<strlen(word[i]); j++) {
            printf("%c", word[i][j]);
        }
    }
  */

    printf("%d", max_result);

    return 0;
}

 

 

연습은 잘될거같다.