Softeer Level 3 비밀 메뉴 2 Python

[21년 재직자 대회 본선]

문제 링크

https://softeer.ai/practice/info.do?idx=1&eid=633 

Softeer

정답 코드

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
listN = input().split()
lenN = len(listN)
listM = input().split()
lenM = len(listM)
maxLength = 0
if lenN > lenM:
    lenN, lenM = lenM, lenN
    listN, listM = listM, listN

dp = [[0 for _ in range(lenM)] for _ in range(lenN)]

cnt = 1
for i in range(lenN):
    for j in range(lenM):
        if listN[i] == listM[j]:
            dp[i][j] += 1

def isValid(r, c):
    return 0 <= r < lenN and 0 <= c < lenM

for c in range(lenM):
    for r in range(lenN):
        if isValid(r, c):
            if isValid(r-1, c-1):
                if dp[r][c]:
                    dp[r][c] += dp[r-1][c-1]
            c += 1


for r in range(1, lenN):
    for c in range(lenM):
        if isValid(r, c):
            if isValid(r-1, c-1):
                if dp[r][c]:
                    dp[r][c] += dp[r-1][c-1]
            r += 1

for d in dp:
    tmpMax = max(d)
    if tmpMax > maxLength:
        maxLength = tmpMax

print(maxLength)

풀이 방법

1. 입력받은 키의 길이에 따라서 listM(긴 리스트)과 listN(짧은 리스트)로 구분한다.

2. memoization을 하기 위해 dp라는 2차원 배열을 만든다.

    - 이유 : for문을 3번 반복하게 되면 3000 * 3000 * 3000의 연산을 해야한다. => 시간초과

3. 2중 for문을 돌면서 현재 값 = listM(긴 리스트)의 i번째 인덱스의 값과 같다면 dp에 저장한다.

4. 저장이 끝난 dp를 다시 대각선으로 확인해줘야 하는데 새로줄과 가로줄에서 시작하면서 비교한다.

    - 행 비교는 r값이 변하고 c값은 0에서 시작

    - 열 비교는 c값이 변하고 r값은 0에서 시작

    - r, c값이 배열을 벗어나지 않게 isValid 함수를 만든다.

    - 대각선이라고 하면 행 + 1, 열 + 1이므로 반복문을 돌 때마다 r += 1 또는 c += 1을 해준다.

    - dp[r][c]의 값을 누적해서 더해준다.

        - 그래야 최대 길이를 확인할 수 있다.

    - dp[r][c]의 값이 0인 경우는 스페셜키가 이어지지 않는다는 말이므로 누적할 필요가 없다.

5. 누적해서 더해준 dp에서 max값을 찾아준다.

느낀점

 "이게 되네?"

사실 아무 생각 없이 같은 값을 다 더해봤다. 그랬더니 어쩐일인지 대각선으로 이어지는 패턴을 확인할 수 있었다. 일단 for문은 당연히 2번이 최대일거라고 생각했고 긴 리스트와 짧은 리스트를 구분했다. 30분 이상 고민하기에는 시간이 너무 짧아서 30분 정도 최대한 고민하다가 안 풀리면 다음에 푸는 방식을 채택해서 행하는 중이다. 일단 풀리면 된거 아니겠어? 가끔 다른거 풀다가 다시 풀면 풀릴 때도 있기 때문에 너무 오래 고민하지는 말자.