.png)
💡 생각하자
Dynamic Programming(동적 계획법)의 개발절차
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기
주어진 예시 '10'에 대해서 생각해보자.
10은 3가지 연산 중에서 '2로 나누기'와 '1을 빼기'를 적용할 수 있다.
그렇다면 '5->1'과 '9->1'에 필요한 연산의 수를 비교하여, 작은 쪽을 선택하고 +1('10/2=5' or '10-1=9')을 하면 '10->1'에 필요한 연산의 수를 구할 수 있다.
이렇듯 '10->9->3->1'에서 '10->1'을 구하기 위해서는 '9->1'이 필요하고, '9->1'은 '3->1', '3->1'은 '1->1'이 필요하므로, bottom-up으로 구하면 된다.
재귀 관계식
M(n) : 정수 n을 1로 만들기위해 필요한 연산의 수
M(n) = minimum(M(n/3), M(n/2), M(n-1)) + 1 (n>=4)
M(1) = 0, M(2) = 1, M(3) = 1
💻 구현하자
- 주어진 n에 각각의 연산을 적용하여 다음 값을 구하는 함수
void convert(int n, int* n1, int* n2, int* n3) {
if (n % 3 == 0) *n1 = n / 3;
else *n1 = 0;
if (n % 2 == 0) *n2 = n / 2;
else *n2 = 0;
*n3 = n - 1;
}- n에 3개의 연산을 적용한 값을 계산하여 각각 n1, n2, n3에 저장한다.
- n1과 n2의 경우, 나눠떨어지지 않으면 0을 저장한다.(이유는 아래에 있다.)
- 초기 호출문
M[0] = INF; M[1] = 0; M[2] = 1; M[3] = 1;
for (int i = 4;i <= n;i++) {
convert(i, &n1, &n2, &n3);
M[i] = minimum(M[n1], M[n2], M[n3]) + 1;
} - M[i]를 구하기 위해서는 M[i/3], M[i/2], M[i-1]을 비교해야 한다.
하지만, 나눠떨어지지 않는 수의 경우에는 이상한 결과가 발생하기 때문에(ex. M[10/3] = M[3])
convert()에서 0을 주고 minimum()에서 INF 값(M[0])을 갖게 해, 비교할 의미를 없게 만든다.
💥 발전하자
- 개선점
- 나눠떨어지지 않는 것에 대해 INF값을 주는 것은 우아하지 않다. 다른 방법(정석적인 방법)은 그냥 if문을 사용하여, 나눠떨어지는 경우에 대해서만 비교하면 된다.
