[백준/7476] 최대 공통 증가 수열 (Python)

Problem : https://www.acmicpc.net/problem/7476

7476번: 최대 공통 증가 수열

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 01:13:58

 

---

 

문제 설명

 

 

정수로 이루어진 두 수열이 있다. 두 수열의 공통 증가 부분 수열 중 가장 긴 것의 길이를 구하는 프로그램을 작성하시오.

길이가 N인 수열 S1, S2, ..., Sn이 길이가 M인 수열 A1, A2, ..., AM의 증가하는 부분 수열이 되려면, 모든 1 ≤ j ≤ N에 대해서, Sj = Aij인 1 ≤ i1 < i2 < ... < iN ≤ M가 존재하고, 모든 1 ≤ j < N에 대해 Sj < Sj+1을 만족해야 한다.

 

 

입력 및 출력

 

입력

 

두 수열의 정보는 각각 두 줄에 걸쳐서 주어지며, 첫째 줄에는 수열의 길이 M이 주어진다. (1 ≤ M ≤ 500) 다음 줄에는 M개의 정수 Ai (-2^31 ≤ Ai < 2^31)가 주어진다.

 

출력

 

첫째 줄에 최대 공통 증가 부분 수열의 길이를 출력하고, 둘째 줄에 그 부분 수열을 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

 

입력 예시

 

5
1 4 2 5 -12
4
-12 1 2 4

 

출력 예시

 

2
1 4

 

 

---

 

풀이

 

DP로 풀이하는 것까진 좋다. 첫 번째 수열의 i번째 num1[i], 두 번째 수열의 j번째 num2[j]가 서로 일치할 때, 1~i번째, 1~j번째의 부분 수열 중 최장 길이 공통 수열의 길이를 DP[i][j]라고 두자. num1[i] != num2[j] 일 때는 DP[i][j] == 0이다. 증가하지 않는 공통 부분 수열의 경우 O(N^2)이 소요되나, 증가 여부를 검사해야 하므로 업데이트에 O(N^4)가 소요된다.

 

즉 가지치기가 중요하다. 바텀업 방식으로 진행하되, num1[i] < num1[k], num1[k] == num2[l]을 만족하는 k, l ( i < k <= N, j < l <= M ) 에 대하여, k를 고정하였을 때 j에 가장 가까운 l 한 경우만 업데이트하는 게 포인트이다.

 

• num2[l] == num2[ l_ ] 를 만족하는 l_에 대하여,  l < l_이 무조건 성립한다. 즉 l과 l_ 사이에 num2[l] 이상의 임의의 수가 하나 이상 존재할 수 있다.
• 따라서 항상 DP[k][l] >= DP[k][l_]임이 자명하다. 따라서 l 하나만을 탐색하여 업데이트하면 경우의 수를 줄여나갈 수 있다.

 

 

풀이 코드(pypy3)

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

dp = [[[0, (-1, -1)] for j in range(M)] for i in range(N)]

for i in range(N) :
  for j in range(M) :
    if N_list[i] != M_list[j] :
      continue
    dp[i][j][0] += 1
    for k in range(i+1, N) :
      if N_list[i] >= N_list[k] :
        continue
      for l in range(j+1, M) :
        if M_list[l] == N_list[k] :
          if dp[k][l][0] < dp[i][j][0] :
            dp[k][l] = [ dp[i][j][0], (i, j) ]
          break

answer, answer_idx, answer_list = 0, (-1, -1), list()

for i in range(N) :
  for j in range(M) :
    if dp[i][j][0] > answer :
      answer, answer_idx = dp[i][j][0], (i, j)

while answer_idx != (-1, -1) :
  answer_list.append((N_list[answer_idx[0]]))
  answer_idx = dp[answer_idx[0]][answer_idx[1]][1]

print(answer)
print(*reversed(answer_list))

풀이 완료!