DP

1. DP로 풀 수 있는 문제 조건

- 큰 문제를 작은 문제로 나눌 수 있다.

- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

 

2. 메모리제이션

- DP 구현 방법 중 하나. 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 저장한 결과를 가져오는 기법 ( caching 기법이라고도 함)

- 이전에 계산된 결과를 일시적으로 기록하는 개념

- top-down방식에 사용되는 기법 ( 재귀함수를 사용하여 큰 문제를 해결하기 위해 작은 문제를 호출)

 

3. top-down / bottom-up

- top-down : 재귀 함수 호출 

- bottom-up : 반복문을 사용하여 작은 문제부터 값을 구해가는 방식. 이 때 결과를 저장하는 리스트를 dp 테이블이라 함

 

4. DP임을 아는 방법

- 완전탐색으로 생각해 보고, 시간이 너무 오래 걸릴 것 같으면 DP를 적용할 수 있는 부분 (부분 문제들의 중복 여부) 확인

- 재귀함수인 top-down을 사용한 경우 recursion depth 관련 오류 발생가능. 이 땐 sys 라이브러리 내 'setrecursionlimit()'함수를 호출해서 재귀 제한을 풀 수 있음

 

 

5. 예제

1) 1로 만들기

- 가능한 연산 방식을 알려주고, 정수 x가 주어졌을 때 1로 만들 수 있는 최소 연산 횟수

- 5로 나누기 / 3으로 나누기 / 2로 나누기 / 1 빼기 연산이 가능할 때 주어진 정수 X를 1로 만들기 위한 최소 연산 횟수

- dp[N] = N을 1로 만들기 위한 최소 연산 횟수 라고 할 때

  if ( N % 5 == 0 ) : dp[N] = min(dp[N/5], dp[N-1]) + 1

  else if ( N % 3 == 0 ) : dp[N] = min(dp[N/3], dp[N-1]) + 1

  else if ( N % 2 == 0 ) : dp[N] = min(dp[N/2], dp[N-1]) + 1

  else dp[N] = dp[N-1] + 1

 

2) 1칸 이상 떨어진 배열 값들의 합

- 배열이 주어져있을 때, 최소한 한 칸 이상 떨어진 index끼리의 합을 구하려 한다. 이 때 구할 수 있는 최대 합

- N까지 있는 배열에서 최대 합 : dp[N] = max(dp[N-1], dp[N-2] + arr[N]) -- N번째 배열을 선택하냐/안하냐 둘 중 하나

 

3) 타일링(바닥공사)

- 1*2, 2*1, 2*2의 타일이 주어질 때, 2*M 크기의 바닥을 채우는 모든 경우의 수

- 반드시? 필수적으로? 해당 타일 모양을 사용해야 할 경우의 수 알아보기 

- 가로 길이가 N만큼 주어지고, 왼쪽부터 N-1만큼 이미 덮어져 있다고 할 때, 나머지를 덮을 수 있는 경우의 수는 1개 (2*1) -- 세로로 긴 것 

- 가로 길이가 N만큼 주어지고, 왼쪽부터 N-2만큼 이미 덮어져 있다고 할 때, 나머지를 덮을 수 있는 경우의 수는 2개

(1*2, 2*2) -- 가로로 긴 것 & 정사각형

- 바로 위의 경우에서  2*1이 없는 이유는 N-1에서 세어줘야 하기 때문! N-1에서 센 걸 N-2에서 또 세면 안됨.  N-1에서 센 거랑 N-2에서 센 건 다른경우다~!

 - dp[N] = dp[N-1] + 2*dp[N-2]

 

4) 동전으로 M원 만들기

- N가지 종류의 화폐가 있을 때, M원을 만들 수 있는 최소한의 화폐 개수는?. 만들 수 없을 땐 -1을 출력

- 이 문제가 그리디가 아닌 이유!!!1 : 그리디려면 큰 단위 화폐가 작은 단위 화폐의 배수여야 한다!!! 

- 각 화폐 값어치가 c1,c2,...cn이라 하면 M원을 만들기 위한 최소 횟수 dp[M] = min (dp[M-c1], dp[M-c2],dp[M-cn]) + 1

dp = [10001] * (M + 1)
dp[0] = 0
coins = [] #화폐 단위

for i in range(M):
	for coin in coins:
    	if (i-coin) >= 0 and dp[i-coin] != -1:
        	dp[i] = min(dp[i],dp[i-coin]) + 1
if dp[M] == 10001:
	print(-1)
else:
	print(dp[M])