[Java] 백준 1339 : 단어 수학

문제 링크

1.

sloved에 그리디 문제로 분류되어 있길래 탐욕스러운 사고기법을 적용해보려 했지만 떠올리지 못했다.

 

해설을 찾아보니 그리디 문제로 풀면 못푼단다.

이 문제의 분류를 수학, 백트래킹으로 바꿔야 할 듯하다.

 

중학교 때 이런 문제와 비슷한 창의 수학 문제를 풀었던 것 같은데.. 흠

 

 

2.

수학적 방식은 매우 심플하면서도 획기적이다.

 

높은 자릿수의 알파벳에 가중치를 부여하는 방식이다.

 

$GCF$ 와 $ACDEB$ 두 가지 단어를 예로 들면,

 

$GCF = 100G+10C+F$

$ACDEB = 10000A+1000C+100D+10E+B$  이므로

 

$GCF+ACDEB = 10000A+1010C+100D+100G+10E+B+F$ 이다.

 

따라서 높은 자릿수인 $A$부터 $9$를 넣으면 단어의 합이 최댓값이 될 것이다.

 

 

3.

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        Integer[] alphabet = new Integer[26];
        
        Arrays.fill(alphabet, 0);

        for (int i = 0; i < n; i++) {
            char[] input = sc.next().toCharArray();

            int pos = 1;
            for (int j = input.length - 1; j >= 0; j--) {
                alphabet[input[j] - 'A'] += Integer.valueOf(pos);
                pos *= 10;
            }
        }

        Arrays.sort(alphabet, Collections.reverseOrder());
        int value = 9, answer = 0;

        for (int i = 0; i < alphabet.length; i++) {
            if (alphabet[i] == 0)
                break;
            answer += alphabet[i] * value--;
        }

        System.out.println(answer);
        sc.close();
    }
}

 

 

4.

int 배열은 초기값이 0이지만, 객체 배열은 초기값이 null이다.

Integer배열을 초기화하지 않고 덧셈을 하려니 오류가 났다.

초기화하고 사용해주도록 하자.

 

[참고] https://mygumi.tistory.com/156