DP - 문제(1)

1로 만들기

https://www.acmicpc.net/problem/1463

어떤 정수 N에 다음 아래와 같은 연산을 선택하여 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 구하여라.

정수 x에 사용할 수 있는 연산은 세가지

1. x가 3으로 나누어 떨어지면, 3으로 나눈다.
2. x가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

점화식 세우기
D[N] = N을 1로 만드는 최소 연산 횟수
N -> N/3 ~> 1 : 1 + D[N/3]
N -> N/2 ~> 1 : 1 + D[N/2]
N -> N-1 ~> 1 : 1 + D[N-1]
셋 중 최소를 구하면 된다.
D[N] = min(D[N/3], D[N/2], D[N-1]) + 1

//top - down
int go(int n) {
	// 1을 1로 만드는 법 = 0
    if (n == 1) return 0;
    if (d[n] > 0) return d[n]; // Memorization
    d[n] = go(n-1) + 1; // N-1 
    if (n%2 == 0) { // N/2
        int temp = go(n/2) + 1;
        if (d[n] > temp) d[n] = temp;
    }
    if (n%3 == 0) {  // N/3
        int temp = go(n/3) + 1;
        if (d[n] > temp) d[n] = temp;
	}
    return d[n];
}

// bottom- up
d[1] = 0;
    for (int i=2; i<=n; i++) {
        d[i] = d[i-1] + 1;
        if (i%2 == 0 && d[i] > d[i/2] + 1) {
            d[i] = d[i/2] + 1;
        }
        if (i%3 == 0 && d[i] > d[i/3] + 1) {
            d[i] = d[i/3] + 1;
        }
    }

시간복잡도 : 함수의 호출 개수(문제의 개수) x 함수의 시간복잡도(문제 1개 푸는데 필요한 시간복잡도 = 점화식을 푸는 시간복잡도 = 단순 3개의 최소값을 구함.)
: N x 1 = O(N)

2 x n 타일링

https://www.acmicpc.net/problem/11726

2 x n 직사각형을 1x2, 2x1타일로 채우는 방법의 수
아래 그림은 2x5를 채우는 방법의 수

점화식 세우기
D[n] = 2xn을 채우는 방법의 수

2xn직사각형이 있을 때, 가장 오른쪽에 타일을 놓을 수 있는 방법은 총 2가지
첫번째 1x2타일 하나(세로 하나) | => D[n-1]

두번째 2x1타일 둘(가로 둘) = => D[n-2]

D[n] = D[n-1] + D[n-2]

2 x n 타일링 2

https://www.acmicpc.net/problem/11727

2 x n 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수
아래 그림은 2x17를 채우는 방법의 수

점화식 세우기
D[n] = 2xn을 채우는 방법의 수

앞의 경우에서 하나의 경우만 더 추가해주면 된다.
세번째 2x2타일 하나 => D[n-2]

D[n] = D[n-1] + D[n-2]*2

1,2,3 더하기

https://www.acmicpc.net/problem/9095

정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제

점화식 세우기
D[n] = n을 1,2,3의 합으로 나타내는 방법의 수

x1 + x2 + x3 + ... + i = n
i에 올수 있는 수는 1,2,3이다.

1. i가 1인 경우 : x1 + x2 + x3 + ... = n-1
2. i가 2인 경우 : x1 + x2 + x3 + ... = n-2
3. i가 3인 경우 : x1 + x2 + x3 + ... = n-3

D[n] = D[n-1] + D[n-2] + D[n-3]
D[0]에는 아무것도 사용하지 않아야 하므로 1이다. (집합의 공집합의 의미랑 비슷함)

시간 복잡도 : O(N)