20494번: 스시

문제 출처 : https://www.acmicpc.net/problem/20494

 

언어 : Kotlin

 

문제 설명 :

천하제일코딩대회를 마치고 N명의 운영진은 회전 초밥집으로 회식을 가서 스시를 먹기로 했다. 이 식당에는 총 26가지의 스시가 있으며, 이는 문자 A부터 Z까지에 대응하여 생각할 수 있다.

회전 초밥집은 아래 그림과 같이 N+1개의 의자와 N+1개의 접시로 이루어져 있다. 사람들은 계속 자신의 자리에 앉아 있으며, 매 분마다 접시들은 시계방향으로 한 칸씩 이동한다.

 
S_0에는 셰프가 앉아 있으며, 매 분마다 셰프는 자신 앞에 온 접시가 비어있지 않으면 아무 행동도 하지 않고, 자신 앞에 온 접시가 비어있으면, 한 점의 스시를 만들어 접시에 올린다. 하지만, 현재 상태에서 셰프가 더 이상 스시를 만들지 않아도 모든 손님이 유한한 시간안에 식사를 마칠 수 있음이 보장된다면, 셰프는 더 이상의 스시를 만들지 않는다.

 N명의 대회 운영진은 각각 S_1, S_2, ...,  S_N의 자리 중 한 곳에 앉았고, 그들 외의 손님은 없다고 가정한다. N명의 대회 운영진 각각은 자신이 오늘 먹고 싶은 스시의 목록이 있고, 목록에 있는 순서대로 먹고자 한다.

매 분마다 각 손님(대회 운영진)은 다음과 같이 행동한다:

자신의 앞에 온 접시에 이번 순서에 먹을 스시가 있으면 먹는다.
아니면, 접시에 손대지 않는다.
초기에 모든 접시는 비어있고, 손님들이 식사를 시작하는(모두 자리에 앉은) 시점부터 셰프는 음식을 만든다고 가정한다.

모든 손님들이 유한한 시간 안에 식사를 마치기 위해 셰프가 만들어야 하는 스시의 최소 개수를 구하여라.

 

입력 :

입력의 첫 줄에 N이 주어진다.
이후 i (1 ≤ i ≤ N)번째 줄에는 손님 i가 먹고 싶어하는 스시의 목록을 나타내는 문자열 B_i가 주어진다.

한 종류의 스시가 한 손님의 목록에 두 번 이상 속할 수 있음에 유의하라.

 

출력 :

문제의 답을 나타내는 정수 하나를 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 1024MB
•  1 ≤ N ≤ 100
• 1 ≤ len(B_i) ≤ 100

 

입출력 예 :

입력	출력
2 ABCDE FGH	8
1 ABCDE	5

 

풀이 : 

문제가 대회니 뭐니 언급하며 길고 어렵게 썼지만 결국은 손님이 먹고 싶은 목록을 다 더한 개수를 나타내는게 아닌가?

싶어 풀어보니 성공했다. 문제가 조금 더 어려우려면 유한한 시간도 주어졌어야할 거 같은데 시간은 없이 만들어야할 스시 개수만 구하니까 이런 것 같기도 하다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var cnt = 0
    repeat(readLine().toInt()) {
        cnt += readLine().count()
    }

    bw.write("$cnt")
    bw.flush()
    bw.close()
}