[Softeer] 21년 재직자 대회 본선 - 비밀메뉴2

문제

이전의 21년 재직자 대회 예선 - 비밀메뉴 문제의 심화 버전인 듯한 문제이다.

 

<배경>

회사 식당에는 전설처럼 전해 내려오는 비밀 메뉴에 대한 소문이 있다. 소문의 내용은 대강 이러하다. 식권 자판기의 버튼을 특정 순서대로 누르고 결제를 하면, 평소와는 다른 색깔의 식권이 나온다. 이 식권을 배식대에 제출하면, 어떤 비밀 메뉴를 받을 수 있다는 것이다. 물론 이를 실제로 본 사람은 아무도 없어서, 어떤 메뉴가 나오는지는 커녕 눌러야 하는 버튼의 순서조차 알려져 있지 않다.

식당의 평범한 이용객인 당신은 이 소문을 들은 순간 비밀 메뉴에 호기심이 크게 동했다. 그 실체를 좇아 연구를 거듭한 지도 어언 몇 달째. 당신은 자판기의 버튼을 아무렇게나 두들기면서, 비밀 메뉴가 나오는 조작법을 두 가지 찾아냈다! 다만 뒤에 서 있던 사람들의 항의로 인해 식권을 사용하지는 못했다.

당신은 이 두 조작법을 연구해 비밀 메뉴 조작법을 찾고자 한다. 당신은 버튼에  $1$이상  $K$이하의 정수로 된 번호를 매겨, 이러한 숫자의 나열로 버튼 조작을 표현했다. 당신의 직감은 둘 모두에 포함된 일련의 조작법 중 가장 긴 것을 찾아야 한다고 말하고 있다.

길이가 각각 $N$과 $M$인 버튼 조작 과정이 주어질 때, 둘 모두에 완전히 포함되는 일련의 조작 과정 중 가장 긴 것의 길이를 출력하여라.

 

<입력>

 

<출력>

비밀 메뉴 조작법으로 가능한 가장 긴 것의 길이를 첫째 줄에 출력한다. 만일 겹치는 조작이 전혀 없다면 0을 출력한다.

---

풀이

요약하면 가장 긴 공통부분 길이를 구하는 것이다.

 

문제 풀이를 위한 핵심 아이디어는 아래와 같다.

$A : a_1, a_2, ..., a_i, ..., a_n$

$B : b_1, b_2, ..., b_j, ..., b_m$

이런 두 문자열에서 $c[i][j]$를 $a_i, b_j$를 끝 글자로 한 공통문자열의 길이를 나타낸다.

$c[i][j]$의 값은 아래처럼 경우를 나눠서 구할 수 있다.

1. $a_i \neq b_j$ : 0

2. $a_i = b_j$ : $c[i-1][j-1]+1$

 

이 알고리즘에 맞는 코드이다.

n,m,k = map(int,input().split())
a = list(input().split())
b = list(input().split())

c = [[0]*m for _ in range(n)]

longest = 0
for i in range(n):
    for j in range(m):
        if a[i] == b[j]:
            if i==0 or j==0:
                c[i][j] = 1
            c[i][j] = c[i-1][j-1] + 1
            longest = max(longest, c[i][j])
print(longest)

 

이 문제가 재직자 대회 본선 1번 문제로 알고 있는데, 그래서 간단한 문제가 출제된 것 같다.