[그리디 알고리즘 Lv.02] 18238번 ZOAC 2

1. 문제
    18238번 ZOAC 2 (링크 참고)

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

18238번: ZOAC 2

 

2019년 12월, 두 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.

작년 ZOAC의 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!

규칙은 이러하다.

• 그림과 같은 원판에 문자들이 순서대로 적혀있다. 처음 순간에 화살표는 'A'를 가리키고 있다.
• 원판은 왼쪽 또는 오른쪽으로 돌릴 수 있다. 원판을 한 칸 돌리는 데에는 1의 시간이 소요된다.
• 화살표가 가리키고 있는 문자를 출력할 수 있다. 문자를 출력하는 데에 걸리는 시간은 없다.

시간이 너무 오래 걸리면 지루해할 ZOAC의 참가자들을 위해 성우는 해당 문자열을 앞에서부터 차례대로 최대한 빠르게 출력하려고 한다.

바쁜 성우를 위하여 해당 문자열을 출력하는 데 걸리는 시간의 최솟값을 구해보자.

 

출처 : 백준 https://www.acmicpc.net/problem/18238

 

 

2. 문제 포인트

• 시작은 'A'에서 시작한다
• 원판을 돌려 문자를 찾을때는 왼쪽 오른쪽 모두 가능하다
  = 가까운 쪽으로 돌려야 최솟값을 구할 수 있다.
• 알파벳은 26글자이다
  현재 글자에서 다음 글자로 넘어갈때 중간값인 13초 넘게 걸리지 않는다
  (왼쪽, 오른쪽 모두 회전이 가능하기에 가까운 방향을 이용한다)

 

3. 접근법

• 각 문자의 좌측으로 이동할때의 소요시간, 우측으로 이동할때의 소요시간을 계산
• 두가지 계산값중 작은값 선택

 

반응형

 

 

4. 결과 코드

import sys

a = sys.stdin.readline().strip()
result = 0

# 소문자 입력에 대비해 대문자로 전환
a = a.upper()

# 시작점이 'A'를 추가
a = 'A' + a

for i in range(len(a)-1):
    # chr_1 = 좌측으로 이동할때의 소요시간
    # chr_2 = 우측으로 이동할때의 소요시간
    chr_1 = ord(a[i+1]) - ord(a[i])
    chr_2 = ord(a[i]) - ord(a[i+1])

    # chr_1, chr_2의 계산값이 음수가 나오는 경우 26을 더해 소요 시간 계산
    ## ex. 'AZ'의 경우 chr_2 = 65-90 = -25 음수가 발생
    ##     26을 더해줌으로 1이 되어 좌측으로 돌린 1이란 소요시간 계산 가능
    if chr_1 < 0:
        chr_1 += 26
    if chr_2 < 0:
        chr_2 += 26
    
    # 좌측 우측 이동 소요 시간중 작은값 선택
    result += min(chr_1, chr_2)
print(result)