챕터3-5. DP | 문제 풀이1 - (4) 백준 No.9095 : 1, 2, 3 더하기

1, 2, 3 더하기 문제

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

문제요약

정수 N이 주어지면 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제

해결방법

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N] = "N을 1, 2, 3의 합으로 나타내는 방법의 수"

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 정수 N이 주어지면 마지막 자리에 3가지 방법 중 1가지를 선택할 수 있다.

N = O+O+O+...+O+O+A

Case1) 맨 뒤 A자리에 1을 조합으로 추가하는 경우
- 1을 조합으로 추가했으므로 N-1을 1, 2, 3의 조합으로 나타내는 것을 다시 찾아내면 됨.

Case2) 맨 뒤 A자리에 2을 조합으로 추가하는 경우
- 2를 조합으로 추가했으므로 N-2을 1, 2, 3의 조합으로 나타내는 것을 다시 찾아내면 됨.

Case3) 맨 뒤 A자리에 3을 조합으로 추가하는 경우
- 3를 조합으로 추가했으므로 N-3을 1, 2, 3의 조합으로 나타내는 것을 다시 찾아내면 됨.

따라서, D[N] = D[N-1] + D[N-2] + D[N-3] 으로 점화식을 생각할 수 있다.
이 점화식은 1, 2, 3 각각을 맨 뒤에 고정시켜두고 생각한다 점에서 2xn 타일링 문제와 같이 이해하면 된다.

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

4. 코드구현
- 배열 d의 초기값을 d[0] = 1, d[1] = 1, d[2] = 2 로 해주는데, d[0] = 1는 d[3]부터 계산값이 맞아돌아가도록 하기 위함이다.
- 앞에서 풀었던 문제들과 다르게 첫번째 if 문에 n <=1 이 아닌 n <=2 를 해줘야 한다.

* Top-Down, Bottom-Up 방식 모두 최종값이 결정되는 순서는 d[1], d[2], d[3],,, 순이다. (구현방식의 차이일 뿐)

<Top-down 방식>

(1) 구현
-> '재귀호출' 방식으로 구현

int d[12] = {1, 1, 2};   // d[0] = 1, d[1] = 1, d[2] = 2, d[4~11] = 0

// d[0] = 1; d[3] = 3인데 이게 정상적으로 작동하려면 d[0]=1이어야 하므로
// d[1] = 1; 원래 d[1]은 1이라서.
// d[2] = 2; 원래 d[2]은 2이라서.

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getAllCombiCount(int n)
{
    if (n <= 2)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        d[n] = getAllCombiCount(n-1) + getAllCombiCount(n-2) + getAllCombiCount(n-3);
        return d[n];
    }
}

(2)시간복잡도
= 배열에 채워 넣어야하는 값의수 x 1칸을 채우는 복잡도
-배열에 채워 넣어야하는 값의 수 : N
- 1칸을 채우는 복잡도 : D[N-1] +D[N-2] + D[N-3] 총 3번의 연산, 이걸 시간복잡도로 나타내면 O(1)
- 따라서 전체 시간복잡도는 N * O(1) = O(N)

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

int d[12] = {1, 1, 2};   // d[0] = 1, d[1] = 1, d[2] = 2, d[4~11] = 0

// d[0] = 1; d[3] = 3인데 이게 정상적으로 작동하려면 d[0]=1이어야 하므로
// d[1] = 1; 원래 d[1]은 1이라서.
// d[2] = 2; 원래 d[2]은 2이라서.

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getAllCombiCount(int n)
{
    if (n <= 2)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        for(int i=3; i <=n ; i++)
            d[i] = d[i-1] + d[i-2] + d[i-3];

        return d[n];
    }
}

(2) 시간복잡도
= for 문의 반복 횟수 = O(N)