BOJ #1339

---

LEVEL :

Gold4

---

문제 요약 :

같은용량의 물병을 합쳐 k개 이하로 만들어야 할 때 추가로 구매해야 하는 물병의 갯수는?

---

해결 방안 :

제일 처음에는 문자열의 길이를 기준으로 정렬을 한 뒤, 순서대로 높은 숫자를 부여하면 가장 큰 조합을 만들 수 있을 줄 알았다.
그렇게 푼 결과 오답이 나왔고 질문검색에서 반례를 보니 큰 실수를 했음을 알았다.
ex)
N=10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB
일때, A=9 이고, B=8 이면 오답이다.
결구 백트레킹을 통해 문제를 해결 해야 함을 알았고,
문자열을 입력받을때, 문자열의 각 문자가 몇번 반복되고, 몇번째 자리수인지를 기록하는 배열을 만들어 9부터 넣어 가장큰 조합을 만들어 내는 알파벳을 찾고 해당 알파벳을 체크하여 넘어가는 방식으로 진행하였다.

---

시간 복잡도 :

1000번미만의 비교로 문제를 해결할 수있다.

---

Solution

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    n = int(input().strip())
    alpha = []
    arr = []
    for i in range(n) :
        s = input().strip()
        for i in range(len(s)) :
            try :
                alpha_idx = alpha.index(s[i])
                idx = len(s)-i-1
                arr[alpha_idx][idx] += 1
            except :
                alpha.append(s[i])
                idx = len(s)-i-1
                new = [0]*8
                new[idx] += 1
                arr.append(new)
    visited = [False]*len(alpha)
    res= 0
    for i in range(9,-1,-1) :
        m = 0
        max_idx = -1
        for j in range(len(alpha)) :
            if visited[j] == True :
                continue
            sum_alpha = 0
            each_arr = arr[j]
            for k in range(8) :
                if each_arr[k] == 0 :
                    continue
                sum_alpha += (10**k)*each_arr[k]*i
            if sum_alpha > m :
                m = sum_alpha
                max_idx = j
        res += m
        visited[max_idx] = True
    print(res)