https://www.acmicpc.net/problem/1339
Greedy한 유형으로 핵심은 문자에 숫자를 대응하기 전에 모든 단어에 같은 알파벳이 얼마나 있는지가 중요하다.
처음에는 가장 왼쪽에 있는 알파벳부터 9를 대입하는 방식을 고안했는데 바로 틀렸다.
반례를 이러하다.
ABBBBBB
B
BBB.....위으 경우와 같이 특정 개수이상 B가 계속 나오는 경우에는 A보다 B의 숫자가 더 커야지 최댓값이 되기 때문에 문자와 숫자를 대응하기 전에 자릿수를 고려하여 문자들을 모두 더해주어야한다.위의 경우 A:10 B:1+1+1+1+1+1+1+1+1+...+1 이렇게 될 것이다.위의 결과를 역순으로 정렬하여 숫자가 큰 곳부터 9를 대입해주면 된다.코드는 다음과 같다.
import sys
input = sys.stdin.readline
n = int(input())
words = []
alpha_info = {}
for _ in range(n):
words.append(input().rstrip())
for i in words:
for j in range(len(i)):
length = len(i)-j-1
if i[j] not in alpha_info:
alpha_info[i[j]] = 10**length
continue
alpha_info[i[j]] += 10**length
alpha_info = list(alpha_info.values())
alpha_info.sort(reverse=True)
ans = 0
idx = 0
for i in range(9,9-len(alpha_info),-1):
ans += alpha_info[idx] * i
idx += 1
print(ans)
처음에 높은 자릿수부터 그냥 9를 대입하여 하나씩 줄여갔는데 그러기엔 어쩐지 골드 4치고 너무 쉽게 풀린다 했다.
바로 틀렸습니다...ㅋㅋ
다행이 반례를 바로 생각해서 고쳤다.
'📚알고리즘 > 백준' 카테고리의 다른 글
[백준 2493번] 탑 (C++) (0) | 2023.05.14 |
---|---|
[백준 1863번] 스카이라인 쉬운거 (C++) (1) | 2023.05.13 |
[백준 1325번] 효율적인 해킹 (C++) (0) | 2023.05.11 |
[백준 18114번] 블랙 프라이데이 (C++) (0) | 2023.05.09 |
[백준 27972번] 악보는 거들 뿐 (C++) (0) | 2023.05.09 |