[백준] 단어 수학 1339 - JAVA

문제

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

1339번: 단어 수학

 

풀이

누적합과 백트레킹을 이용한 문제이다.

 

visit 배열의 size는 26으로 나타나게 하므로써 visit배열의 인덱스가 알파벳이 된다.

visit 배열을 누적합으로 나타낸다. 이렇게 하므로써 각 문자마다 다른 값을 갖게된다.

예를들어, ACDEB라고 한다면 visit배열은 다음과 같게 될것이다.

1

2

3

4

5

A는 1, B는 2, C는 3, D는 4, E는 5를 갖게 될것이다.

이 visit 배열의 값은 alphabetResult 배열의 index가 된다. 
alphabetResult 배열에는 0~9까지 들어간다. 즉, 알파벳의 값이 된다.

따라서 A가 나타내는 숫자는 alphabetResult [1] 값이 된다.

이 alphabetResult 배열의 값은 backTracking으로 구한다.

코드

import java.io.*;
import java.util.*;

public class Main {	 

	static int n;
	static int visit [] = new int [26];
	static int check[] = new int[10];
	static String strArr[];
	static int alphabetResult [] = new int [11];
	static int max = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		strArr = new String[n];
		
		for(int i=0;i<n;i++) {
			strArr[i] = br.readLine();
			for(char c : strArr[i].toCharArray()) {
				visit[c-'A'] = 1;
			}
		}
		
		for(int i=1;i<26;i++) {
			visit[i] += visit[i-1];
		}
		
		back(1);
		System.out.println(max);
	}
	
	static void back(int idx) {
		if(idx == 11) {
			int result = 0;
			for(int i=0;i<n;i++) {
				int sum = 0;
				for(char c : strArr[i].toCharArray()) {
					sum = sum * 10;
					sum += alphabetResult[visit[c - 'A']];
				}
				result+= sum;
			}
			max = Math.max(max, result);
			return;
		}
		for(int i=0;i<10;i++) {
			if(check[i] == 0) {
				check[i] = 1;
				alphabetResult[idx] = i;
				back(idx+1);
				check[i] = 0;
			}
		}
	}

	
}