dynamic programming 3

* 틀린 내용이 있을 시 지적 부탁드립니다.

문제는 더블릿 21 dynamic programming에 있는 land입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/land/land.php?pname=land

이전에 풀었던 다차원 배열 1 문제 fishing보다 진화된 문제입니다.  물론 그때처럼 풀면 안됩니다.  dp 문제인 만큼 어떻게든 반복된 연산을 줄이고 이전에 계산한 값을 이용할 수 있어야 합니다.

조금 다른 점은 네모칸 안의 숫자의 합이 아니라 범위의 크기이고 각 칸의 최소최대차의 제한이 있습니다.

여기선 대표적으로 2개의 배열을 쓰겠습니다.  하나(A)는 해당 열에서 어느정도의 한계치가 주어졌을 때 포함할 수 있는 높이를 저장합니다.  다른 하나(B)는 해당 열의 이전 행 값입니다.

전자는 2차원 배열, 후자는 1차원 배열입니다.  

에제를 예시로 보겠습니다.

먼저 초기화를 하기위해 첫 줄을 받습니다.  10, 15, 4를 받는 부분이 아닌 41, 40, 41...을 받는 부분입니다.

10, 15, 4는 변수명으로 w, h, l로 하겠습니다.

B배열의 1행 0~끝열까지 첫 줄의 값을 넣고 A배열의 값을 모두 1로 초기화 합니다.  A배열의 행은 받아들이는 수의 열이 되고 열은 한계값인 l이 됩니다.  각 열의 값마다 0~한계값 l까지의 인덱스에 해당하는 값을 더했을 때 한계값 l을 넘지 않는 범위를 구할겁니다.

두번째 줄부터는 실제 계산을 해야합니다.  

먼저 A배열을 이용해 지금 받아들이는 열의 B배열을 초기화 해줄겁니다.

두번째 줄 39를 받아들였을 경우,

이전 행, 같은 열 41과의 차이는 41-39=2 입니다.

그럼 다음 행, 같은 열이 들어왔을 때 1열까지의 범위를 포함하기 위해서는 2행, 3행의 차가 0, 1, 2까지 허용됩니다.

이를 이용해 B배열을 채워주는데 지금과 같은 경우는 B배열 0행에 0, 1, 2열의 값은 이전 값의 2, 3, 4열의 값에 해당합니다.  이 2, 3, 4는 2와 의 차가 0~한계치 사이에 포함되는 값입니다.

이전 행과의 차가 -1일 경우

new B  old B

0    

1       =    0

2       =    1

3       =    2

4       =    3

이 되고 새 0열에는 1을 넣게됩니다.  이는 이전까지의 한계치가 0, 1, 2, 3이었을 경우 그값에 +1을 해서 현재 1이상 차이가 나는 값들에 넣는다는 것을 의미합니다.

이전 행과의 차가 1일 경우

가져오는 old B의 인덱스는 1, 2, 3, 4가 됩니다.  

맨 왼쪽은 위 숫자와 아래 숫자의 차이고 위 숫자가 같은 행 이전열의 값, 아래 숫자가 현재 받은 숫자입니다.  그리고 오른쪽 0~4까지는 B배열의 인덱스이고 그 위의 동그라미 친 숫자가 그 인덱스가 가지고 있는 현재 값인데 잘 안보이네요...  41일때를 처음으로 보고 1로 초기화 한 상태입니다.  

맨 밑의 42일 경우 B배열의 4인덱스가 5의 값을 가짐으로서 41부터 모든 높이를 가질 수 있음을 나타냅니다.  

왼쪽의 36은 0과 1인덱스가 4로 맨위 41과는 5의 차이가 나므로 높이로 포함하지 못합니다. 즉 B배열의 현재 값의 각 인덱스는 다음에 들어올 숫자와 이정도의 차이가 났을 때 어느정도의 높이인지를 가지고 있고, 숫자가 들어오면 B배열에서 허용할 수 있는 차이값을 인덱스로 보고 그 값에서 +1한 값을 대입합니다...

이렇게 숫자를 받을 때마다 해당 열의 B배열을 갱신합니다.  B배열에선 각 행의 0~l의 값이 갱신됩니다.  그리고 받은 값은 A배열의 현재열의 인덱스에 넣어줍니다.

그 후 0~l만큼 현재 받은 값에서 행의 좌측으로 이동하면서 차를 계산합니다.

4행 5열을 받은 경우 4행 5열과 4행 4열, 4행 5열과 4행 3열, 이렇게 차를 계산하면서 자신의 열과 옆의 열이 포함하는 높이(B배열)의 값중 작은 값으로 

현재열-좌측열*작은값

공식으로 포함되는 넓이를 계산합니다.

현재열의 B배열의 각 값들은 다음에 받을 같은 열의 값에도 적용이되지만 좌측열의 값에도 적용이 된다는 점을 이용하면 됩니다.

이후 넓이가 가장 클 때의 값을 출력하면 됩니다.