[B]BOJ11048 , dp 뿌수기

실전 문제에는 해결할 수 있는 로직이 더 숨겨져있다.

직관적으로

1, 2차원 dp table

2. 초기값

3, 재귀 구조를

알려주지 않는다.

알고리즘 테스트를 풀면서 이를 난이도 차이를 더 크게 체감하게되어서

다시 dp기초부터 복습하고자 한다.

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

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구한다.

미로의 사탕 크기에 대한 규칙이 따로 없기에
Greedy 한 방법,
즉, 사탕의 개수가 큰 곳으로만 이동하는 방법이 최적해라는 보장이 없다.
따라서 Greedy 한 접근 방법은 제한다.
어떤 방법을 이용했을 때, 최댓값이 아니라면
처음부터 재계산하는 것이 아니라
중간지점부터 시작한다.
즉, 중간지점 이전에 계산해 놓았던 값을 활용한다.

-> memoization

-> recursive
memoization에 활용할 자료구조는
미로의 모양대로 2차원 배열 table[i][j]의 i=n, j = m에 저장할 수 있다.
dp table에서 초기값을 정의할 수 있다. base case
재귀 관계식을 정의할 수 있다. recurrence

문제를 읽고 위 요건들이 정의되었다면

재귀를 사용할 준비가 되었다.

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

어떤 지점 i, j에서의 dp[i][j]는 그 지점에서 준규가 가진 사탕의 최대 개수이다.

그리고 이 값은 문제에서 직관적으로 제시해준다.

(실전 문제는 좀 더 문제 속에 숨어있다.)

준규는 현재 (1, 1)에 있고,

(N, M)으로 이동하려고 한다.

준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고,

각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다.

준규의 시각에서는
1. (r+1, c)
2. (r, c+1)
3. (r+1, c+1)로 나아가는 것이지만

dp_table [i][j]입장에서는 다음과 같이 업데이트 될 수 있다.
1. dp_table[i][j] = dp_table[i-1, j] + maze[i][j]

2. dp_table[i][j] = dp_table[i, j-1] + maze[i][j]

3. dp_table[i][j] = dp_table[i-1, j-1] + maze[i][j]

여기서 최적해는 사탕의 최대 개수이므르로

dp_tabel[i-1, j] dp_table[i, j-1] . dp_tabel[i-1, j-1] 중 하나를 선택하는데

가장 큰 값을 선택할 것이다.

max(dp_table[i-1, j] dp_table[i, j-1], dp_table[i-1, j-1] )

maze[i][j]는 이미 입력받은 값이므로 변하지 않는다.

그리고 max(dp_table[i-1, j] dp_table[i, j-1], dp_table[i-1, j-1] ) 내의

dp_table[i-1, j] 들은 재귀적인 점화 식으로 표현이 가능하다.

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

<최상단 제출> : Top-down, recursive function

<하단 제출> : Bottom-up, nested for loop

Computation suite