자, 지난번 강좌에 나왔던 연습문제는 푸셨는가?

 그럼 풀이법에 대해 설명하도록 하겠다.

 이 문제도 동적계획법으로 풀린다.(당연하지.. 동적계획법 강좌에 나온 문젠데) 풀이법은 1차원 Up sequence문제와 별로 다를 것이 없다. 우선 이차원 배열 L(2차원 버젼이므로)을 다음과 같이 잡는다.

 L[i , j] = i행 j열에 있는 숫자로 끝나는 오름차순 수열의 최대길이

 1차원 버젼과 별로 다르지 않다.

 그럼 점화식은?

 L[i , j] = 1

 L[i , j] = maximum( L[k1 , k2] + 1 )

 역시 1차원 버젼과 다를것은 별로 없다.(음.. 그러고 보니 "다를것이 없다"라는 말을 지난 강좌에서부터 너무 많이 쓰고 있는 듯..-_-) 그 전까지의 최대길이에 조건을 만족할 경우 +1해주면 되는 것이다.

 그럼 소스를 보자.

program Upsequence_2D;

const

    n=5;

    data : array[1..n,1..n] of integer =(

        (1,2,3,4,5),

        (8,5,4,10,9),

        (7,2,9,3,20),

        (21,22,6,19,11),

        (10,5,20,12,11)

    );

var

   L : array[1..n,1..n] of integer;

   i,j,k1,k2 : integer;

   max : integer;