백준(BOJ) 3663 고득점(Python)

문제 내용.

 

그리디 문제.

문제의 핵심은 A로만 이루어진 가장 긴 구간을 찾는 것이라고 생각했다.

이미 A인 문자를 방문하는 것 자체가 손해이기 때문이다.

처음에는 해당 구간만 찾아서 문제를 푸려고 했는데, 길이가 같은 최장 구간이 여럿인 경우에는 문제가 발생했다.

그래서 브루트포스를 적용했다.

모든 문자에 대해서 인덱스가 증가하는 방향으로 가장 가까운 A가 아닌 문자를 찾고, 정방향과 역방향 두 방향을 고려해 이동 횟수를 계산해줬다.

그 중 최솟값을 최종적인 이동 횟수로 설정하게 되면, 결국은 A로만 이루어진 최장 구간에 대한 이동 횟수가 나오게 될 것이다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

for _ in range(int(input())):
    S=input().rstrip()
    ans=0
    for i in S:
        ans+=min(ord(i)-65,91-ord(i))
    move=len(S)-1
    for i in range(len(S)):
        p=i+1
        while p<len(S) and S[p]=='A':
            p+=1
        move=min(move,i+i+len(S)-p,(len(S)-p)*2+i)
    print(ans+move)

브루트포스는 아닐 것 같아서 그리디로만 풀어보려고 했는데, n이 작아서 계산해보니 O(t*n^2)인 브루트포스로도 가능했다.