[ BOJ ] 3407 : 맹세 ( SILVER 2 ) / Python

문제

위대한 화학자 김선영은 그를 바라보며 굳은 맹세를 했다.

난 오늘부터 원소 기호로 이루어진 단어만을 말할 것이다.

선영이는 "I Am CLaRa"를 말할 수 있다. I 는 아이오딘, Am은 아메리슘, C는 탄소, La는 란타넘, Ra는 라듐이다. 또, 선영이는 "InTeRnAtIONAl"도 말할 수 있다. 하지만, "collegiate", "programming", "contest"는 원소 기호로 이루어진 단어가 아니기 때문에 말할 수 없다.

단어가 주어졌을 때, 선영이가 말할 수 있는 단어 인지 (원소 기호가 연결된 단어) 아닌지를 구하는 프로그램을 작성하시오. (대소문자는 가리지 않는다)

다음은 이 문제에서 사용하는 원소 주기율표이다.

H

He

Li

Be

B

C

N

O

F

Ne

Na

Mg

Al

Si

P

S

Cl

Ar

K

Ca

Sc

Ti

V

Cr

Mn

Fe

Co

Ni

Cu

Zn

Ga

Ge

As

Se

Br

Kr

Rb

Sr

Y

Zr

Nb

Mo

Tc

Ru

Rh

Pd

Ag

Cd

In

Sn

Sb

Te

I

Xe

Cs

Ba

*

Hf

Ta

W

Re

Os

Ir

Pt

Au

Hg

Tl

Pb

Bi

Po

At

Rn

Fr

Ra

**

Rf

Db

Sg

Bh

Hs

Mt

Ds

Rg

Cn

Fl

Lv

* 란타넘족

La

Ce

Pr

Nd

Pm

Sm

Eu

Gd

Tb

Dy

Ho

Er

Tm

Yb

Lu

** 악티늄족

Ac

Th

Pa

U

Np

Pu

Am

Cm

Bk

Cf

Es

Fm

Md

No

Lr

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 T개의 줄에는 알파벳 소문자로만 된 단어가 하나 주어진다. 단어의 길이는 50,000을 넘지 않으며 양수이다.

출력

입력으로 주어진 단어가 선영이가 발음할 수 있는 단어라면 YES를, 아니라면 NO를 출력한다.

풀이 과정

dp를 이용하여, i 번째 문자까지를 원소 기호로 이루어진 단어로 말할 수 있는지 여부를 dp[i]에 저장한다.

두 글자인 원소 기호도 있으니 유의해서 dp를 쌓는다. 두 글자로 말하는 방법 때문에 앞에 dp를 먼저 쌓기 때문에 값이 꼬일 수도 있다는 것을 생각하자.

arr = ['H', 'He', 'Li', 'Be', 'B', 'C', 'N', 'O', 'F', 
'Ne', 'Na', 'Mg', 'Al', 'Si', 'P', 'S', 'Cl', 'Ar',
'K', 'Ca', 'Sc', 'Ti', 'V', 'Cr', 'Mn', 'Fe', 'Co', 
'Ni', 'Cu', 'Zn', 'Ga', 'Ge', 'As', 'Se', 'Br', 'Kr',
'Rb', 'Sr', 'Y', 'Zr', 'Nb', 'Mo', 'Tc', 'Ru', 'Rh', 
'Pd', 'Ag', 'Cd', 'In', 'Sn', 'Sb', 'Te', 'I', 'Xe',
'Cs', 'Ba', 'Hf', 'Ta', 'W', 'Re', 'Os', 'Ir', 'Pt', 
'Au', 'Hg', 'Tl', 'Pb', 'Bi', 'Po', 'At', 'Rn',
'Fr', 'Ra', 'Rf', 'Db', 'Sg', 'Bh', 'Hs', 'Mt', 'Ds', 
'Rg', 'Cn', 'Fl', 'Lv', 'La', 'Ce', 'Pr', 'Nd',	
'Pm', 'Sm', 'Eu', 'Gd', 'Tb', 'Dy', 'Ho', 'Er', 'Tm', 
'Yb', 'Lu', 'Ac', 'Th', 'Pa', 'U', 'Np', 'Pu', 'Am', 
'Cm', 'Bk', 'Cf', 'Es', 'Fm', 'Md', 'No', 'Lr']
dic = {}
for s in arr:
    now = s.lower()
    dic[now] = 1

import sys
input = sys.stdin.readline

n = int(input().rstrip())
for _ in range(n):
    string = input().rstrip()

    dp = [0 for _ in range(len(string))]
    for i in range(len(string)):
        if i == 0:
            if dic.get(string[i]):
                dp[0] = 1
            if len(string) > 0 and dic.get(string[i]+string[i+1]):
                dp[1] = 1
        else:
            if dic.get(string[i]):
                dp[i] = max(dp[i], dp[i-1])
            if i + 1 < len(string) and dic.get(string[i]+string[i+1]):
                dp[i+1] = max(dp[i+1], dp[i-1])
    
    #print(dp)
    print('YES' if dp[-1] == 1 else 'NO')