[백준] 1339 단어 수학

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

1339번: 단어 수학

2022-02-25

---

1. 백트래킹

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main1339 {
    public static int N, answer;
    public static int[] arr, word;
    public static boolean[] vtd;
    public static HashSet<Character> set; // 중복 단어 거르기
    public static ArrayList<String> list; // 계산해아할 단어들
    public static void solve() {
        int calc = 0;
 
        for(int i = 0; i < list.size(); i++) {
            String str = list.get(i);
            int num = 0;
            for(int j = 0; j < str.length(); j++) {
                num *= 10;
                num += arr[str.charAt(j)-65];
            }
            calc += num;
        }
 
        answer = Math.max(answer, calc);
    }
 
    public static void comb(int cnt) {
        if(cnt == set.size()) {
            solve();
            return;
        }
 
        for(int i = 9; i >= 9-word.length+1; i--) {
            if(!vtd[i]) {
                vtd[i] = true;
                arr[word[cnt]] = i;
                comb(cnt+1);
                vtd[i] = false;
            }
        }
 
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
 
        N = Integer.parseInt(st.nextToken());
        set = new HashSet<>();
        list = new ArrayList<>();
        answer = 0;
 
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine().trim());
            String str = st.nextToken();
            // 중복 알파벳
            for(int j = 0; j < str.length(); j++) set.add(str.charAt(j));
 
            list.add(str);
        }
 
        List<Character> tmp = new ArrayList<>(set);
 
        word = new int[set.size()]; // 나온 단어들
        arr = new int[27]; // 단어 조합 만들 것
        vtd = new boolean[10];
        for(int i = 0; i < set.size(); i++) {
            word[i] = tmp.get(i) - 65;
        }
 
        comb(0);
 
        System.out.println(answer);
    }
}

 

2. 수학

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main1339_2 {
    public static int N, answer;
    public static int[] arr;
    public static String[] word;
    public static HashSet<Integer> set;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
 
        N = Integer.parseInt(st.nextToken());
        arr = new int[26];
        word = new String[N];
        set = new HashSet<>();
 
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine().trim());
            String str = st.nextToken();
            word[i] = str;
            int num = 1;
            for(int j = str.length()-1; j >= 0; j--) {
                arr[str.charAt(j)-65] += num;
                num *= 10;
            }
        }
 
        Arrays.sort(arr);
 
        int val = 9;
        for(int i = arr.length - 1; i >= 0; i--) {
            answer += arr[i] * val--;
        }
 
        System.out.println(answer);
    }
}

 

#문제풀이

 

1. 백트래킹

문제로 나온 N개의 단어들 중에서 중복을 제거한 알파벳들을 기준으로 만들 수 있는 모든 조합을 구했다. 그리고 9부터 차례대로 숫자를 부여해보고 합을 계산해 본 후, 그 합 중 최댓값을 출력했다. 

 

2. 수학

풀고 나서 다른 사람들 풀이를 보니, 백트래킹 브루트포스가 아닌 방법으로 푼 사람들이 있어서 그 방법으도 풀어봤다. 숫자들을 미리 다 자릿수를 합쳐서 계산한 후 정렬해서 큰 수 부터 차례대로 9, 8, 7, ..  숫자를 계산 해주었다. 

 

2
GCF
ACDEB

 

예를 들어

GCF의 경우 100G, 10C, 1F 이고 

ACDEB의 경우 10000A, 1000C, 100D, 10E, 1B이다. (line 25 ~ 28)

 

즉, 10000A, 1B, 1010C, 100D, 10E, 1F, 100G가 된다. 이걸 정렬 한 후 9부터 차례대로 숫자를 계산해주면 된다. (line 31 ~ 36)

 

 

2번 방법의 시간이 1번의 방법보다 1/10 줄었다.