목차

고득점

ps
링크acmicpc.net/…
출처BOJ
문제 번호3663
문제명고득점
레벨골드 4
분류

그리디

시간복잡도O(T*n)
인풋사이즈T<=100, n<=1000
사용한 언어Python
제출기록30860KB / 96ms
최고기록76ms
해결날짜2022/01/17

풀이

코드

"""Solution code for "BOJ 3663. 고득점".

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

Tags: [Greedy]
"""

ORD_A = ord('A')


def main():
    T = int(input())
    for _ in range(T):
        name = input()

        u_d_count = sum(min(ord(c) - ORD_A, ORD_A - ord(c) + 26) for c in name)
        if u_d_count == 0:
            print(0)
            continue
        t = [i for i, c in enumerate(name) if c != 'A']
        l_r_count = len(name) - t[0]
        for i in range(len(t) - 1):
            left, right = len(name) - t[i + 1], t[i]
            l_r_count = min(l_r_count, left * 2 + right, right * 2 + left)
        l_r_count = min(l_r_count, t[-1])

        print(u_d_count + l_r_count)


if __name__ == '__main__':
    main()

,