사용자 도구

사이트 도구


ps:problems:boj:1036

36진법

ps
링크https://www.acmicpc.net/problem/1036
출처BOJ
문제 번호1036
문제명36진수
레벨골드 1
분류

그리디

시간복잡도O(nm)
인풋사이즈n<=50, m<=50
사용한 언어Python
제출기록29200KB / 80ms
최고기록56ms
해결날짜2021/06/03

풀이

  • 모든 숫자들을 10진수로 변환한다. 그 과정에서 36개의 digit들에 대해서, 각각을 Z로 바꿨을때 전체 합이 얼마나 증가하는지를 추가로 계산한다.
  • 숫자들의 합을 구하고, 구해놓은 증가량중 가장 큰 K개를 추가로 더해준다.
  • 마지막 단계에서 10진수를 36진법으로 변환할 때, 0도 정확히 '0' 으로 변환될 수 있도록 주의할 것.
  • 시간복잡도는 10진수 변환과 증가량 계산에 O(N*M) (M=수의 최대 자릿수), 증가량중 가장 큰 K개를 구하기 위해서 정렬하는 데에 O(ClogC + K) (C=36). 상수인 C는 무시하면, O(NM)

코드

"""Solution code for "BOJ 1036. 36진법".

- Problem link: https://www.acmicpc.net/problem/1036
- Solution link: http://www.teferi.net/ps/problems/boj/1036
"""

DIGITS = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'


def to_base36(num):
    if num == 0:
        return '0'
    ret = []
    while num:
        num, r = divmod(num, 36)
        ret.append(DIGITS[r])
    return ''.join(reversed(ret))


def main():
    N = int(input())
    nums = [input() for x in range(N)]
    K = int(input())

    dec = {x: i for i, x in enumerate(DIGITS)}    
    increase = [0] * 36
    dec_sum = 0
    for num in nums:
        r = 1
        num_in_dec = 0
        for ch in reversed(num):
            ch_in_dec = dec[ch]
            num_in_dec += ch_in_dec * r
            increase[ch_in_dec] += (35 - ch_in_dec) * r
            r *= 36
        dec_sum += num_in_dec
    total_increase = sum(sorted(increase, reverse=True)[:K])
    answer = to_base36(dec_sum + total_increase)
    
    print(answer)
    

if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
I Z A C D
 
ps/problems/boj/1036.txt · 마지막으로 수정됨: 2021/06/03 16:36 저자 teferi