동적프로그래밍(DP)

MatrixPath

Contents

 소년 스티브 잡스는 주말 동안 밤새 열혈코딩을 하느라고 월요일 아침에 늦잠을 자고 말았다. 오전에 수업이 있는 스티브잡스는 빌게이츠와의 경쟁에서 이기기 위해서는 수업에 지각을 하면 안된다. 스티븐 잡스는 머리를 굴리기 위해 지도를 펼쳤다. 

 지도는 왼쪽 가장 위쪽의 좌표가 (1, 1)이고 오른쪽 가장 아래쪽의 좌표가 (4, 4)이다. 각 셀의 숫자는 택시가 움직이는데 드는 시간이다. 즉, (1, 1)에서 택시가 이동하는데 드는 시간은 6이다. 잡스는 (1, 1)의 위치에 있고, 학교는 (4, 4)에 있다. 즉, (1, 1)에서 (4, 4)로 이동해야 한다. 

  그런데 잡스가 사는 동네의 택시는 사람들의 안전을 위해서 다음과 같은 방식으로 움직인다. 

  ㆍ오른쪽이나 아래쪽으로만 이동할 수 있다.

  ㆍ왼쪽, 위쪽, 대각선 이동은 할 수 없다. 

  잡스가 학교에 빨리 가기 위해서는 경로상 걸리는 시간의 합이 최소가 되어야 한다. 여러분이 잡스를 도와야하는 일은 출발점에서 도착점까지의 여러 경로 중 가장 빨리 도착 할 수 있는 시간을 구하는 것이다. 

Input

첫 줄에는 지도의 크기 n*m(<=100)이 들어온다. 

그 다음 n 줄에는 각 셀의 시간이 들어온다. 각 줄은 해당 행의 시간으로 구성된다.

Output

(1,1)에서 (n,m) 까지 여러 경로 중 가장 빨리 도착 할 수 있는 시간을 출력한다.

Sample Input

4 4

6 7 12 5

5 3 11 18

7 17 3 3

8 10 14 9

 

Sample Output

40

=================================================================

PebbleSum

Contents

  소년 스티브 잡스는 심심해서 보드게임을 사러 갔다. 보드게임 가게 주인장은 새로 나온 게임이라면서 "조약돌 놓기" 게임을 소개 시켜주었다. 게임의 규칙은 다음과 같다. 

1. 3*N 테이블의 각 칸에는 양 또는 음의 정수가 기록 되어 있다.

2. 조약돌을 놓는 방법

  ㆍ각 열에는 적어도 하나의 조약돌을 놓아야 한다

  ㆍ가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다.

  퍼즐에 능수능란한 재능을 지녔던 스티브 잡스는 조약돌을 보드 판에 놓기 시작했다. 얼마 지나지 않아서 스티브 잡스는 규칙을 파악 할 수 있었고 모든 경우의 수를 구하여 조약돌을 놓는 것은 삽질 이라는 것을 깨달았다. 그리고 문제의 최종적인 목표는 규칙에 맞게 조약돌을 놓고 조약돌이 놓인 자리의 모든 수를 더했을 때 그것이 최대가 되는 것을 구하는 것이다. 

  여러분이 할 일은 스티브 잡스를 도와 최대값을 구하는 프로그램을 작성하는 것이다.

Input

첫 줄에는 보드판의 가로 크기 m (m<=100)이 들어온다. 

그 다음 3줄에는 각 행의 원소값이 들어온다. 

Output

규칙에 맞게 조약돌을 놓고 그 합의 모든 경우의 수중 가장 큰 값을 출력한다.

Sample Input

8

6 7 12 -5 5 3 11 3

-8 10 14 9 7 13 8 5

11 12 7 4 8 -2 9 4

 

Sample Output

106

=================================================================

MatrixMultiplication

Contents

  소년 스티브 잡스는 최근에 나온 디아블X3를 밤새 하다가 잠이 들어 버렸다. 디아블X3에 너무 광분한 나머지 꿈속에서도 소년 스티브 잡스는 지옥에 빠졌다. 지옥의 이름은 행렬지옥. 행렬지옥의 보스몹(로우컬럼)을 잡기 위해서는 스티브 잡스가 가지고 있는 사과를 던지거나, 주어진 행렬들을 가장 최소의 횟수로 곱해야 한다. 

  스티브 잡스는 너무 배가 고파서 가지고 있는 사과를 다 먹었기 때문에 어쩔 수 없이 행렬을 곱해야 한다. 행렬 A(3*2), B(2*4), C(4*3) 이 순서대로 주어 질 때 이를 곱하는 방법은 두가지 이다.

 1. (A*B) * C

 2. A * (B*C) 

  첫 번째 방법에서 총 곱셈 수는 (3*2*4) + (3*4*3) = 60 번이다. 두 번째 방법은 (2*4*3) + 3*2*3 = 36 이다. 따라서 두번째 방법으로 행렬을 곱해야지만 로우컬럼이 스스로 자폭하게 된다. 

  여러분이 할일은 로우컬럼이 생산한 N개의 행렬를 모두 곱하는데 드는 최소 횟수를 스티브 잡스에게 알려주는 것이다. 

Input

첫째줄에 연산을 수행할 행렬 n(1<=n<=100)을 입력받는다.

두번째줄부터 n개의 행렬의 행 col(1<=col<=100)과 열 row(1<=row<=100)를 공백을 사이에 두고 입력받는다.

Output

행렬연산의 최소 횟수를 출력한다.

Sample Input

4

3 5

5 1

1 8

8 4

Sample Output

59

=================================================================

LCS

Contents

  생명공학연구소에 입사한 컴공 졸업생 길동이에게 염기서열의 유사도를 조사하라는 임무가 내려졌다.

염기서열의 종류가 너무 많아 비교하기가 어려워 고심하던 길동이는 3학년 알고리즘 시간때 배운 LCS(최장공통부분순서) 알고리즘을 생각해냈다.

 

이 문제에서는 동적프로그래밍을 이용해 두개의 염기서열을 비교하여 LCS 길이를 출력하는 프로그램을 짜보도록 한다.

        a a b c c q w w

        |           |  |  |

   qww a          q w w b

Input

비교하고자 하는 두 염기서열 a, b를 입력 받는다. 염기서열 a,b={'a'...'z'}

Output

주어진 두 문자열의 LCS길이를 출력한다.

Sample Input

aabccqww

qwwaqwwb

Sample Output

4