단어와 주기율표

시간 제한1초메모리 제한128 MB

요약
각 단어를 원소 기호 열로 나누는데, 대소문자를 구분하지 않고 조각 수가 가장 적고 그다음 원자번호 합이 가장 작은 분해를 고른다.
난이도

보통10점 중 6점

유형
동적 계획법, 문자열, 해시맵
정답자
아직 제출이 없습니다

문제

주기율표와 여러 단어가 주어질 때, 각 단어를 주기율표에 있는 원소 기호들의 나열로 나타내는 프로그램을 작성하시오.

나타내는 방법이 여러 가지라면 다음 기준을 순서대로 적용한다.

  1. 사용한 원소의 개수가 가장 적은 것을 고른다.
  2. 개수가 같다면, 원소량(사용한 원소들의 번호의 합)이 가장 작은 것을 고른다.

위 두 기준을 모두 적용한 뒤에도 나타내는 방법이 둘 이상 남거나, 애초에 단어를 원소 기호로 나타낼 수 없다면 Too Obvious를 출력한다.

원소 기호는 항상 대문자 한 글자로 시작하고, 그 뒤에 0개 이상의 소문자가 이어진다. 단어를 원소 기호와 맞출 때 글자의 대소문자는 구분하지 않는다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 다음과 같이 구성된다.

  • 첫째 줄에 원소의 개수 OO가 주어진다.
  • 다음 OO개 줄에 원소 기호가 한 줄에 하나씩 주어진다.
  • 그다음 줄에 단어의 개수 PP가 주어진다.
  • 다음 PP개 줄에 단어가 한 줄에 하나씩 주어진다.

OO, PP, 그리고 각 단어와 원소 기호의 길이는 모두 50005000보다 작다. 원소는 원소 번호 순서대로 주어지며, 번호는 11부터 시작해 11씩 증가한다.

출력

각 단어에 대해, 그 단어를 나타내는 원소 기호들을 순서대로 출력한다. 원소를 구분하기 위해 각 원소 기호는 대괄호 []로 감싼다. 나타내는 방법을 하나로 정하는 규칙은 문제 설명을 따른다. 나타낼 수 없거나 방법이 유일하지 않으면 Too Obvious를 출력한다.

예제1

  1. 예제 1

    입력
    1
    4
    Ba
    Na
    N
    A
    2
    banana
    nan
    
    예상 출력
    [Ba][Na][Na]
    [Na][N]