CodeDrive

문제:

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력:

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

풀이방법:

dfs와 DP를 같이 사용해서 이 문제를 풀었다. 기본적인 방식은 dfs를 사용해서 조건에 맞게 이동을 하며 최종 목적지까지 탐색을 한다. 그러다가 최종 목적지에 도달하면 재귀를 빠져나오면서 그 경로에 +1을 해주면서 다시 돌아오게 된다. 

이 과정을 가능한 모든 경우에 대해서 수행할 수 있기 때문에 최종적으로는 dp[0][0]에 저장되어 있는 값을 출력해주면 된다.

문제링크:

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

문제:

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력:

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.

풀이방법:

 앞에서 부터 덧셈, 뺄셈을 수행하면서 0이나 20을 넘어가는 수가 발생하면 저장을 하지 않는 DP 방식으로 풀면 된다. 0~20의 배열을 생성한 뒤에 한 step이 지나갈 때마다 덧셈, 뺄셈을 한 수를 집어 넣는다. 그림으로 보면 다음과 같다.

1) 첫 행은 첫 값을 이용해 다음과 같이 초기화 한다.

2) 다음 행은 이전 행의 1 값에 대해서 덧셈과 뺄셈을 반복한다.

3) 0과 20을 넘어가는 숫자가 있다면 제외한다.

2)와 3) 과정을 반복하고, dp[n-2][numbers[n-1]]을 출력하도록 한다.

문제링크:

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

문제:

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력:

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력:

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

풀이방법:

 자두가 움직일 수 있는 횟수는 W로 초는 T로 고정되어 있기 때문에 열은 W이고, 행은 T인 DP 테이블을 만들어서 이 문제를 해결하도록 한다.

 계속해서 움직이지 않는 경우는 1에서만 점수가 오르기 때문에 1일때만 이전 행의 0열 값을 가져와 1을 더하도록 한다. 1번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 짝수일 때 카운트가 오르게 되고, 2번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 홀수일 때 카운트가 오르게 된다. (1번나무에서 초기에 위치하기 때문)

문제링크:

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

문제:

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

입력:

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력:

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)

풀이방법:

N명이 있을 때, 발생하는 경우의 수를 점화식으로 구하면 DP[N] = DP[N-1]+DP[N-2]와 같이 구할 수 있다.

그리고 VIP들 같은 경우에는 움직이지 못하기 때문에 주위 사람들과 자리 변경이 불가능하다. 따라서 양 옆을 분할한다라고 생각할 수 있다. 즉 문제에서 소개한 예시로 보면 9개의 자리가 있을 때, 4와 7에서 자리를 분할하고 있다. 이제 이 문제는 DP[3] * DP[2] * DP[2]와 같이 경우의 수를 구하면 된다.

문제링크:

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

문제:

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력:

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력:

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

풀이방법:

그냥 이 함수를 재귀로 구성하면 시간초과가 발생하게 된다. 따라서 각 결과를 dp 테이블에 저장함으로써 시간을 단축시키도록 한다.

문제링크:

www.acmicpc.net/problem/9184

문제:

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력:

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력:

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이방법:

www.acmicpc.net/problem/2293 의 동전 1 문제를 응용해서 풀면 된다. 이 문제에서는 k원을 만드는 경우의 수를 구하는 문제였지만, 이 문제에서는 최솟값을 구해야 한다. 따라서 동전의 가치가 최대 100,000원이므로 초기값으로 100,001원(0원은 0으로 초기화 한다.) 으로 설정하고, 작은 동전부터 사용해서 각 p원을 만들 수 있는 최소 갯수를 구하도록 한다.

 이 문제의 예시로 생각하면 다음과 같다. (1,5,12)원이 있을 때, 1원으로 15원을 만드는 방법은 다음과 같이 비교할 것이다.

 위 표는 다음 두 조건을 비교하면서 채워나갔다. 1원을 만드는 경우로 예시를 든다.

1. 현재 값을 그대로 사용한다. dp[1]

2. 0원에서 1원을 더해서 사용한다. dp[1-1]+1

3. 1과 2중 더 작은 값을 사용한다. min(dp[1],dp[1-1]+1)

즉 이를 일반화 하면 다음과 같다. min(dp[n],dp[n-c]+1), n은 현재 만들고자 하는 금액, c는 현재 사용하고 있는 동전의 가치다.

 5원을 사용하는 경우는 1~4원은 만드는 것이 불가능하므로 5원부터 반복한다.

 12원을 사용하는 경우는 1~11원은 만드는 것이 불가능하므로 12부터 반복한다.

 최종적으로는 dp[k]원이 초기화한 값에서 변경이 되었다면 dp[k]를 출력하고, 바뀌지 않았다면 -1을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/2294

문제:

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력:

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

풀이방법:

0으로 초기화 된 DP 배열을 미로의 값에 따라 초기화 하면서 진행하면 된다.

이 문제의 예제를 통해서 설명한다. 처음에는 다음과 같이 초기화 된다.

numbers[0]의 값은 1이므로 dp[1]의 값을 업데이트한다.

numbers[1]의 값은 2이므로 dp[2]~dp[3]의 값을 업데이트한다.

numbers[2]의 값은 0이므로 넘어가고, numbers[5]까지 반복하면 아래와 같이 된다.

 만약 이미 dp[i+j]에 0이 아닌 다른 값이 초기화되어 있다면, dp[i+j]값과 dp[i]+1값 중 작은 값을 사용하도록 한다. 끝까지 진행하면 다음과 같이 된다.

 위 작업을 모두 반복했을 때, 맨 마지막 값이 0이 아닌 다른 값으로 바뀌었다면, 끝에 도달할 수 있는 것이므로 해당 값을 출력하면 되고, 아니라면 -1을 출력하도록 한다. 그리고 생각해야 하는 예외가 두가지가 있다.

 첫번째는 5 (0,0,0,1,0)과 같은 경우가 있다. 이런 경우는 if dp[i]==0 and i!=0 와 같은 조건문을 넣어서 해결해준다. 정상적으로 진행될 때, dp에 0 값은 dp[0]을 제외하고 생기면 안되기 때문이다.

 두번째는 1 (0) 이다. 이 경우에는 시작과 동시에 오른쪽 끝으로 도달한 경우이기 때문에, 마지막 출력하는 단계에서 예외처리로 0을 출력하도록 한다.

문제:

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다.

이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다.

두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최댓값은 7이다.

입력:

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1 ≤ B ≤ 2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.

출력:

얻을 수 있는 최종 점수의 최댓값을 출력한다.

풀이방법:

 DP를 사용해서 풀어야 하는 문제다. 처음에는 재귀로 이 문제를 접근했었는데, 시간초과랑 메모리 초과가 반복적으로 발생해서 반복문을 사용해서 풀게 되었다. 반복문을 사용해서 풀게 될 경우에는 정방향으로 DP를 배치하는 것이 아닌, 역방향으로 DP를 구성해야 한다고 한다. 마치 재귀로 풀이 되던 것들이 반복문으로 풀어져서 풀이 된다고 생각하면 된다.

문제링크:

www.acmicpc.net/problem/10835

문제:

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 불어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표가 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력:

첫째 줄에 N(1<=N<=100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0,1,2,3,4,5,6,7,8,9 중의 하나가 된다.

출력:

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

풀이방법:

 가로의 길이가 세 개로 고정되어 있기 때문에 그림의 세 조건에서 파란 동그라미에 해당하는 부분들에서 값을 가져와서 최댓값과 최솟값을 계산하면 된다.

 하지만 이 문제에는 메모리 제한이 걸려 있었는데, N이 최대 100,000까지 존재하기 때문에 초기에 이 배열을 모두 초기화하고 더해나가면 메모리 초과가 발생하게 된다. 따라서 처음부터 N만큼의 배열을 초기화하지 않고, 한 줄씩 입력 받으며 최댓값과 최솟값을 바꾸어 나가도록 한다.

0번째 인덱스에서는 이전 행의 0번째와 1번째 값에만 영향을 받으며,

1번째 인덱스는 이전 행 전체에서,

2번째 인덱스는 이전 행의 1번째와 2번째 값에만 영향을 받는다.

max와 min을 사용해 각 칸을 tuple 형식으로 업데이트 했다. (max값, min값) 그리고 마지막에서는 max와 min의 key 옵션을 활용해서 전체 최대 점수와 최소 점수를 구하도록 했다.

문제링크:

www.acmicpc.net/problem/2096

문제:

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력:

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력:

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

풀이방법:

LCS(Longest Common Subsequence)는 여러 개의 수열 모두의 부분수열이 되는 수열들 중 가장 긴 것을 찾는 문제다. 만약 이 문제를 가능한 모든 경우를 비교해본다면 엄청 큰 시간복잡도를 가지게 될 것이다. 따라서 이를 DP를 사용해서 시간복잡도를 줄이도록 한다.

문자열 ACAYKP와 CAPCAK를 테이블로 추적하며 LCS 함수의 정의를 알아본다. 

1. 우선 부분수열이 비어있는 경우도 존재할 수 있기 때문에 각 문자열에 0번째 인덱스를 추가한다. (0ACAYKP, 0CAPCAK)

그 후 문자열들의 크기(len(string1) x len(string2))만큼의 0행렬을 초기화한다.

2. 세로축의 문자열이 C라고 고정하고, 가로축의 문자열을 하나씩 증가하면서 부분수열을 찾는다.

(C와 A 중 LCS 값, C와 AC 중 LCS 값, C와 ACA 중 LCS 값, ....)

그러면 표는 아래와 같이 값이 구해지게 될 것이다.

이제 세로축의 문자열을 하나씩 늘리고, LCS 함수의 규칙에 따라 진행을 하면 다음과 같이 표들을 얻을 수 있다.

• LCS(CA,ACAYKP)

• LCS(CAP,ACAYKP)

위 표들은 다음 2가지 케이스에 대해서 업데이트 되는 것을 알 수 있다.

1. 두 부분 수열들이 같은 원소로 끝나는 경우
   1. LCS(CAP,ACAYKP)중 CAP과 ACAYKP를 비교할 때가 이 경우의 예시다. 이 때 맨 마지막 P가 일치한다. 이러한 경우에는 두 부분수열에서 P를 제거한다. 그러면 연산해야 하는 LCS는 다음 두 부분수열이다. (CA, ACAYK)
   2. 이 부분수열의 LCS는 CA임을 이전 행들에서 알 수 있다.
   3. 삭제했던 부분수열 P를 다시 붙이면 CAP이 되고, 이것이 CAP과 ACAYKP의 LCS다.
   4. 이를 LCS의 길이를 구하는 표에서 보면 왼쪽 위 값에 1을 더한것과 같다.
      1. if str1[i]==str2[j], then LCS[i][j]=LCS[i][j]+1와 같다.
2. 두 부분 수열들이 같은 원소로 끝나지 않는 경우
   1. LCS(CAP,ACAYKP)중 CAP과 ACA를 비교하는 경우다. 이 때는 각 부분수열들의 맨 끝 문자를 제거한 뒤에 둘 중 큰 LCS를 택하면 된다.
   2. 즉, max(LCS(CA,ACA), LCS(CAP,AC))와 같다.
      1. 따라서 LCS(CA,ACA)는 CA이므로 LCS(CAP,ACA)는 CA가 된다.

따라서 이 규칙들에 따라서 끝까지 진행하면 다음과 같다.

따라서 LCS의 길이만 구하고 싶다면 4가 답이 된다.

만약 subsequence 문자열을 알고 싶다면 각 행을 역추적하면서 가장 큰 숫자가 시작 된 곳을 체크한다.(값이 일치하면서 +1 된 곳이기 때문이다.)

따라서 ACAK가 LCS임을 알 수 있다.

문제링크:

www.acmicpc.net/problem/9251