[백준][1339번]단어 수학[JAVA]

문제 설명

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

풀이 방법

• 백트래킹 + 구현문제였다.
• 문자열의 값을 부여하면서, 모든 경우의 수를 만들어보면서 최대값을 찾으면 된다.

알아야되는 개념

• 백트래킹
• 문자열

import java.util.*;
import java.io.*;
public class Main {
    static int N,M;
    static String alpha[] = new String[12];
    static boolean check[] = new boolean[30];
    static int check_alpha[] = new int[30];
    static int arr[] = new int[12];
    static int board[] = new int[30];
    static int ans=-1;
    static void dfs(int depth){
        if(depth == M){
            int idx = 0;
            for(int i=0;i<M;i++){
                for(int j=idx;j<30;j++){
                    if(check_alpha[j] == 1){
                        board[j] = arr[i];
                        idx = j+1;
                        break;
                    }
                }
            }
            sol();
        }
        else{
            for(int i=0;i<=9;i++){
                if(check[i]) continue;
                    arr[depth] = i;
                    check[i] = true;
                    dfs(depth + 1);
                    check[i] = false;
            }
        }
    }


    static void sol(){
        int sum = 0;
        for(int i=0;i<N;i++){
            StringBuffer temp = new StringBuffer();
            StringBuffer s = new StringBuffer();
            s.append(alpha[i]);
            for(int j=0;j<s.length();j++){
                temp.append(board[s.charAt(j) - 'A']);
            }
            String s1 = temp.toString();
            sum+= Integer.parseInt(s1);
        }
        ans = Math.max(sum, ans);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for(int i=0;i<N;i++){
            alpha[i] = br.readLine();
            StringBuffer s = new StringBuffer();
            s.append(alpha[i]);
            for(int j=0;j<s.length(); j++){
                if(check_alpha[s.charAt(j) - 'A'] == 0) {
                    check_alpha[s.charAt(j) - 'A'] = 1;
                    M++;
                }
            }
        }
        dfs(0);
        System.out.print(ans);
    }
}