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

문제링크

---

21년 재직자 대회 본선 | 비밀 메뉴2

풀이과정

---

permutations를 사용할까 했는데 시간초과가 뜰 것 같아 고민을 했다.

그래서 입력받은 비밀메뉴버튼과 그 후에 입력받은 버튼의 끝나는 지점을 고정하고 비교를 했다.

>>> menu : a1, a2, ... , ai, ..., an
>>> button: b1, b2, ..., bj, ..., bm

이 있을 때 ai와 bj에서 끝나는 가장 긴 공통 문자열의 길이를 C[i][j]라고 해보자.
ai와 bj의 길이가 다르면 0, 만약 같다면 서로 다른 값이 나올 때 까지 그 이전을 찾아가서 값을 찾아준다.
이걸 계속 앞으로 돌아가며 반복하는게 아니라, C[i-1][j-1]에 계산이 되어있는 값에 1을 더하면 값을 금방 찾을 수 있다.

예를 통해서 보면 이해하기 쉽다 !
입력 예제가 첫쨋줄 4 10 3, 둘쨋줄 2 1 3 2, 셋쨋줄 1 3 2 1 3 2 1 3 2 1일때 C[i][j]이다.

>>> C
[0, 0, 1, 0, 0, 1, 0, 0, 1, 0]
[1, 0, 0, 2, 0, 0, 2, 0, 0, 2]
[0, 2, 0, 0, 3, 0, 0, 3, 0, 0]
[0, 0, 3, 0, 0, 4, 0, 0, 4, 0]

코드

---

import sys

N, M, K = map(int, sys.stdin.readline().split())
menu = list(map(int, sys.stdin.readline().split()))
button = list(map(int, sys.stdin.readline().split()))
C = [[0] * M for _ in range(N)]

result = 0
for i in range(N):
    for j in range(M):
        if menu[i] == button[j]:
            if i == 0 or j == 0:
                C[i][j] = 1
            else:
                C[i][j] = C[i-1][j-1] + 1
            result = max(result, C[i][j])

print(result)

결과

---