DP

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS Longest Common Subsequence 분석 풀이 import sys input=sys.stdin.readline sys.setrecursionlimit(10000) a=list(input()) a.pop() b=list(input()) b.pop() # 점화식 테이블 d=[[0 for j in range(len(b)+1)] for i in range(len(a)+1)] # LCS 저장 리스트 re..

2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이1 """ 이진수 0으로 시작하지않음 1이 두번 연속으로 나타나지 않음. 11을 부분 문자열로 갖지않음 이친수 : 1, 10, 100, 101, 1000, 1001 이친수X : 0010101, 101101 N(1~90)자리의 이친수의 개수 구하기] """ import sys input=sys.stdin.readline n=int(input()) d=[[0 for i in range(2)] for j in range(n+1)] d[0][0]=0 # ..

1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 분석 n개의 "a", m개의 "z", k번째 문자열 출력 조합점화식 : dp[i][j] = dp[i-1][j]+dp[i-1][j-1] 현재 자릿수에서 a를 선택했을 때 남아 있는 문자들로 만들 수 있는 모든 경우의 수를 T라고 가정 나머지 문자열을 만들 수 있는 경우의 수 = D[남은문자 총개수][남은 z개수] T와 K를 비교해 문자 선택 T ≥ K : 현재 자리 문자를 a로 선택 T < K : 현재 자리 문자를 z로 선택하고, K-=T로 업데이트 N = 3, M = 2,..