[BOJ][DP] 1937. 욕심쟁이 판다

문제 -> https://www.acmicpc.net/problem/1937

처음에는 메모이제이션 생각을 안하다가 

혹시 탐색으로 풀어야 하나 해서 

해봤더니 바로 성공..

너무 틀에 박힌 생각만을 해온것이 아닌가 걱정이다. 

재귀도 꼭 고려해보자 이 놈아  ㅠㅠ

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

메모이제이션, 즉 메모화 재귀도 

DP에 포함되는 분야다. 

메모이제이션이 무엇이냐 하면은,..

간단히 말해서

재귀 호출로 인한 어떤 값을 저장하여 

똑같은 값을 얻으려 재귀가 시도될 때 

연산을 하지않고, 그 기억된 값을 사용하는 것 .

즉, 중복을 없앤다. 

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

어떻게 푸냐 하면은

1. 그 곳에 있는 대나무 값이 현재 내 위치의 값보다 큰지 비교.

2. 크다면, dp값을 비교해서 현재 위치의 dp값이 더 크거나 같으면, 

그 비교한 dp위치에 현재 dp값 + 1을 한다.

3. 순차적으로 1.1 ~ N.N 위치의 값을 시작으로 반복.

*주의 점은, 모든 dp배열이 0으로 초기화 되있기에 

마지막에는 값을 출력할 때 +1을 꼭 해줘야 한다.

문제에 있는 예시를 가지고 조금만 설명 해본다.

주변에 죄다 작으므로 패스.

주변에 죄다 크므로 +1.

죄다 작으므로 패스

이런식으로 문제가 해결된다.

소스(Github)