[코테준비] 현대차&현대모비스: [21년 재직자 대회 본선] 비밀 메뉴2 python

• 문제링크: https://softeer.ai/practice/info.do?idx=1&eid=633&sw_prbl_sbms_sn=255181

개인적으로 현대 코테사이트에 있는 캐릭터들이 귀여운 것 같다. 곰돌이인지 다람쥐인지는 아직 모르겠지만.

 

문제를 보고 젤 먼저 생각 난 방법은 O(N*M*N) 방법이였는데, 이는10*9를 넘는 방법이기에 안된다 판단하고, 풀이를 찾아봤다. 역시 풀이가 별로 없지만, 한양대 교수님의 영상은 있었다! 처음봤을 때 이해가 안가도 예시문제를 하나하나 대입해서 해보면 이해가 갈 것이다. 

• 영상 풀이: https://www.youtube.com/watch?v=mk11yBUiM6I

 

위의 영상풀이를 바탕으로, 내가 푼 방법이다.  아래 코드에 설명을 주석처리해서 써놨으니, 바쁘신 분들은 이것만 봐도 될 것 같다. :)

• 파이썬 풀이 

import sys

# input 받기-----
n, m, k = map(int, sys.stdin.readline().split())
nn = list(map(int, sys.stdin.readline().split()))
mm = list(map(int, sys.stdin.readline().split()))

# 답 구하기 ----
# (1) 필요한 변수
longestn = 0 # 최대값 초기화 - 계속 업데이트 예정
c=[[0]*m for _ in range(n)] # n*m 행렬 # n이 i까지, m이 j까지 올때까지 가장 많이 겹치는 수열의 길이(=longestn의 후보보)
a=[[1,2],[2,3], [333,55]]

# (2) 각 번호를 보며 값 채우기
for i in range(n):
    for j in range(m): 
        if nn[i] == mm[j]:
            # (3) 값이 같으면, 겹치는 수열의 길이 +1
            if i==0 or j == 0:
                # 이때 어느하나라도 0 이면, 시작점이므로 0+1
                c[i][j] = 1
            else:
                # 둘 중 어느하나도 시작점이 아니면, 그전에(c[i-1][j-1]) 겹치는 수열의 길이를 확인 후 거기에 +1
                c[i][j] = c[i-1][j-1] +1 
        # (3) logestn 업데이트
        longestn = max(longestn, c[i][j])
# (4) 정답 출력력
print(longestn)