[백준/파이썬] 13711번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 13711번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] 이다.
1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때, 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.
입력 요약
첫째 줄에 두 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄에는 수열 A에 들어있는 수가, 셋째 줄에는 수열 B에 들어있는 수가 주어진다.
출력 요약
두 수열의 LCS의 크기를 출력한다.
코드
from bisect import bisect
n = int(input())
s1, s2 = list(map(int, input().split())), list(map(int, input().split()))
s1 = {s1[i]:i for i in range(n)}
s3 = [0]*n
for i in range(n):
s3[i]=s1[s2[i]]+1
s2 = [0]+s3
dp, ai, di, c = [0]*(n+1), [0]+[n+2]*(n), [0]*(n+1), 0
for i in range(1, n+1):
if ai[c] < s2[i]:
dp[i] = di[c]+1
c+=1
di[c]=c
ai[c] = s2[i]
else:
idx = bisect(ai, s2[i], lo=0, hi=c+1)-1
dp[i] = di[idx]+1
ai[dp[i]] = min(ai[dp[i]], s2[i])
print(c)
설명
핵심은 구현 관점에서 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기