[Baekjoon] 9251. LCS [G5]

📚 質問する

https://www.acmicpc.net/problem/9251

📌 1回目の解(時間がかかる)

最長共通部分数列(LCS)の問題は、2つの数列が与えられたときに、すべての部分数列の中で最も長い数列を検索することです.
文字列は大文字のみで構成されます.

Input

ACAYKP
CAPCAK

最初の文字列を巡り、アルファベットをキーとし、インデックスリストを値とするディックシーケンスを作成します.
ACAYKP{A:[0, 2] C:[1] Y:[3] K:[4] P:[5]}2番目の文字列を順番に巡回し、ディックシーケンスで値を検証します.出現する数値のうち、dpに出現するindexがより少ない数値では、最値+1と現在の最値と比較されます.
Cが最初に入力されると、最初の文字列ではCが最初のインデックスであるため、最初のインデックスには1が加算されます.
index012345C (1)1A (0, 2)P (5)C (1)A (0, 2)K (4)
Aは0と2、0は左ではないので1、2は左なので1+1=2です.
index012345C (1)01A (0, 2)112P (5)C (1)A (0, 2)K (4)
Pは5で、左の最大値は2に1を加えます.
index012345C (1)01A (0, 2)112P (5)1123C (1)A (0, 2)K (4)
Cは1で、左側の1に1を加えます.
index012345C (1)01A (0, 2)112P (5)1123C (1)1223A (0, 2)K (4)
Aは0,2なので0は変わらず、2は左の最大値で、2に1を加えます.
index012345C (1)01A (0, 2)112P (5)1123C (1)1223A (0, 2)1233K (4)
Kは4で、左が一番大きい3プラス1です.
index012345C (1)01A (0, 2)112P (5)1123C (1)1223A (0, 2)1233K (4)12343
完了後、DP値のうちの最値4を出力する.
上記の手順で解決します.

📒 コード#コード#

arr1 = list(input())    # 첫 번째 문자열
arr2 = list(input())    # 두 번째 문자열

dic = {}                # 딕셔너리에 첫 번째 문자열의 문자는 key에 값에는 인덱스들을 리스트로 넣어준다.
for i in range(len(arr1)):
    if dic.get(arr1[i]):    # 있던 값일 때 추가
        dic[arr1[i]] += [i]
    else:                   # 처음 나왔을 때
        dic[arr1[i]] = [i]

dp = [0 for _ in range(1005)]   # dp 초기화
for s in arr2:      # 두 번째 문자열 순회
    v_arr = dic.get(s)  # 문자의 첫번째 문자열에서의 인덱스들의 집합
    if v_arr:   # 리스트가 있을 때
        dic2 = {}       # 값을 나중에 바꿔주기 위함
        for v in v_arr:
            if v:       # v가 0이 아닐 때
                dic2[v] = max(max(dp[0:v]) + 1, dp[v])  # 왼쪽에 있는 수 중 가장 큰 값 +1과 현 위치의 값 중 비교해 더 큰 값을 선택
            else:       # v가 0일 때
                dic2[0] = 1
        for v in v_arr: # 값을 한꺼번에 바꿔준다.
            dp[v] = dic2[v]

print(max(dp))  # 가장 큰 값 출력

🔍 結果

時間がかかります.

📌 修正の解答

もっと気持ちのいい方法を考えなさい.
インデックスで置換するのではなく、横座標で1番目の文字列を表し、2番目の文字列でdpを2次元と表す.
また、横方向の値と縦方向の値が同じ場合は左上隅の値に1を加え、異なる場合は上向きの値と左側の値を比較してより大きな値を入れる.
0なら、単独で処理するよりもダウンジャケットを入れて解決します.
表で説明する.

Input

ACAYKP
CAPCAK

左Cに等しい場合、左上隅の値に1を加算します.
0ACAYKP00000000C001APCAK
異なる場合は左上の値を比較して入れます.
0ACAYKP00000000C0011111APCAK
この過程を繰り返す.では、最高価格は右下に残ります.
0ACAYKP00000000C0011111A0112222P0112223C0122223A0123333K0123344
したがって出力4.

📒 コード#コード#

arr1 = ' ' + input()    # 첫 번째 문자열
arr2 = ' ' + input()    # 두 번째 문자열

dp = [[0] * (len(arr2)) for _ in range(len(arr1))]   # dp 초기화
for i in range(1, len(arr1)):      # 두 번째 문자열 순회
    for j in range(1, len(arr2)):
        if arr1[i] == arr2[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[-1][-1])

🔍 結果

最低価格で見る演算が減り、時間が大幅に短縮されました.