백준 1036번 python 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드 2

---

풀이

 이 문제는 1339번을 풀어본 기억이 있어 쉽게 풀 수 있었다. 1339번 문제는 각 자릿수를 알파벳으로 바꾸고, n개의 숫자들을 더한 후, 알파벳에 숫자들을 매핑시켰을때의 최댓값을 구하는 문제이다. 자세한건, 문제 풀이한 글을 읽어보도록 하자.

백준 1339번 C++ 풀이

 

1339번 문제와 유사하게, 이번 문제는 더 확장된 느낌이다. 0-9와 A-Z(10-35)로 이루어진 n개의 36진수 중에서, 특정 숫자 k개를 모두 Z로 바꾸었을때의 최댓값을 구하는 문제이다.

 

 문제를 보자마자 1339번 문제의 풀이를 떠올렸다. 그 문제는 알파벳으로 이루어진 숫자들을 모두 더한다. 각 알파벳을 수학의 변수로 본다면, 계산후에는 어떠한 식이 생길 것이다. 말로 하니 설명이 좀 어려워 간단한 예시를 들면 ABC + CBA 라는 덧셈을 하면, 101A + 20B + 101C로 바꿀 수 있다. 이제 계수를 내림차순으로 정렬하여 각 알파벳에 숫자를 할당하면 된다.

 

 이 문제도 비슷하다. 러프한 풀이 설명은 다음과 같다. 0-9와 A-Z를 위처럼 변환한다. 그러면 위처럼 식을 만들 수 있다. 계수가 가장 큰 숫자부터 K개를 Z로 바꾸고, 이를 다시 36진수로 바꿔주면 된다.

 

 여기서 방심할만한 포인트는 계수가 같을 때, 그리고 계수가 가장 큰 K개의 숫자중에서 원래 Z가 있는 경우, 그리고 k가 사용된 문자의 종류보다 많은 경우를 처리해야한다. 사실 내가 구현한 부분에선 앞선 두개가 한번에 처리된다.

 

 위에서 사용한 예시를 그대로 사용해보자. 어짜피 36진수이기도 하기 때문이니까. ABC + CBA ↔ 101A + 20B + 101C 였다. 이때, 우리는 단 한개의 숫자만을 Z로 바꿔서 최댓값을 만들어야 한다. 그런데 계수가 101로 A와 C가 공통으로 제일 크다. 무엇을 선택해야 할까? 답은 A이다. C를 Z로 바꾸는것보다 A를 Z로 바꾸는 것이, 증가량이 더 크기 때문이다. 문자로 보니 어려울 수 있다. A = 10, C = 12, Z = 35이다. 10을 35로 바꾸는게 더 크다는 것을 숫자로 보니 좀 이해가 될 것이다.

 

 아무래도 36진수 숫자의 길이가 최대 50이기 때문에, 입력으로 들어올 수 있는 36진수의 최댓값을 10진수로 변환하면 36^50 - 1이다. 이 값이 얼마인진 중요하지 않지만, 해당 값은 10진수 78자리정도의 숫자이며, gcc에서 지원하는 __uint_128이라는 최대 2^128-1까지 저장할수 있는 이 숫자도 38자리의 숫자를 저장할 수 있다. 그래서 난 과감히 파이썬을 사용하기로 했다. 원래는 C++로 풀지만... 큰 수 사칙연산 구현이 너무 귀찮다. 그래서 평소에는 거의 C++만 사용하지만, 큰 수와 같이 파이썬을 사용하는것이 더 편하다고 생각이 들때는 파이썬을 바로 사용하는 편이다. 파이썬은 숫자의 제한이 (거의)없기 때문에, 이를 깡그리 무시하고 내가 원하는 정수를 저장할 수 있었기 때문이다.

 

 따라서 N개의 숫자에서 각 자릿수에 위치한 문자의 계수를 모두 합하여 저장한다. 0-Z가 순차적으로 저장된 배열에서 해당 문자의 인덱스를 찾으면, 그것이 해당 문자의 10진수 값일 것이다. 이를 활용해서 저장했다. 이후, 계수 내림차순으로 정렬할 것인데, 단순히 계수로만 비교하는 것이 아닌, 해당 문자의 값을 Z로 바꿨을때, 얼마나 크게 증가하는지, 그러니까 Z - (문자) 의 값을 계수에 곱해주어 정렬했다. 이 과정에서, 해당 문자가 Z라면, 0이 곱해지기 때문에, 자연스레 정렬결과의 맨 뒤에 위치하게 된다.

 

 k가 사용된 문자의 종류보다 많을 수 있기 때문에, 그점에 유의해야 한다. Z로 변환한 후, 10진수로 변환하는 과정에서, 우리가 최대로 돌아야 하는 인덱스의 범위는 min(k, 사용된 문자의 종류)이다. 우선 해당 범위까지는 Z로 합하고, 이후에 k가 더 작았다면, 남은 범위는 원래대로 계산하면 될 것이다.

코드

import sys
import string

I=lambda:sys.stdin.readline().strip()

tmp = string.digits+string.ascii_uppercase # 0-Z가 저장된 배열
def dec_to_base(n, b) :
    q, r = divmod(n, b)
    if q == 0 : return tmp[r]
    else : return dec_to_base(q, b) + tmp[r]

n = int(I())
nums = [I() for _ in range(n)]
k = int(I())
g = {}

for num in nums:
    for n, b in enumerate(num[::-1]):
        if b in g : g[b] += 36**n
        else : g[b] = 36**n

nums = sorted(g.items(), key=lambda x : (tmp.find(x[0]) - 35) * x[1])

n = 0
idx = 0

while idx < k and idx < len(nums):
    n += 35 * nums[idx][1]
    idx += 1

while idx < len(nums) :
    n += tmp.find(nums[idx][0]) * nums[idx][1]
    idx += 1

print(dec_to_base(n, 36))