백준 알고리즘, 9095 문제

---

개요

이 문제는 이전 타일링 문제들과 아주 유사한 방식으로 풀어낼 수 있다.

이전 두 문제의 연습결과 쉽게 풀어낼 수 있었다.

마찬가지로 유념해야할 점은

규칙을 찾아내야 한다는 것이다.

---

풀이

어떤 수 N 을 1, 2, 3 으로 더하는 총 개수를 구해야 한다.

이전 문제들과 유사하게 이미 구한 값을 사용한다는 개념을 보면 규칙이 보인다.

4 의 경우

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

1 + 3

2 + 1 + 1

2 + 2

3 + 1

로 총 7가지의 경우의 수가 존재하는데

이것은 다음과 같이 바꿔서 볼 수 있다.

1 + (N - 1 을 1, 2, 3 으로 나타내는 경우의 수)

2 + (N -2 를 1, 2, 3 으로 나타내는 경우의 수)

3 + (N - 3 을 1, 2, 3 으로 나타내는 경우의 수)

점화식은 

DP[N] = DP[N-1] + DP[N-2] + DP[N-3]

이다.

계산에서 N-3 을 필요로 하기때문에 나는 반복문을 3 부터 시작하면 모든 수를 구할 수 있다.

---

주목할 부분

알고리즘과는 관계없이 코드에 효율면에서 생각해볼 부분이 있다.

이 문제는 테스트 케이스를 포함하는데

모든 테스트 케이스를 순회하며 DP[] 연산을 반복하면

같은 DP[] 연산을 계속해서 반복하게 된다.

예를 들면

만약 3개의 테스트케이스를 받고, 4 7 10 의 n 을 입력받는다면

첫번째 4 의 경우에서 반복문은

for ( i = 3 to 4 ) 

로 순회하며 DP[] 를 연산한다.

두번째 경우에 반복문은

for ( i = 3 to 7)

로 순회하며 DP[] 를 연산한다.

그러면 이미 계산된 DP[3~4] 부분이 또다시 구해지게 된다.

Dynamic Programming 이 "기억하며 풀기" 라는 명칭으로 번역되는 만큼

이 부분은 아주 비효율적이라고 생각된다.

아예 깔끔히 해결하고자 한다면

2 X n 타일링 1번 문제에서 구현해보았던 Memoization 방법을 이용해야 한다.

간단히 반복연산만 피하고 싶다면

for 문을 테스트 케이스 이전에 한번에 구해놓고 각 테스트 케이스는 자신의 index 만 출력해주면 된다. (물론 필요없는 케이스까지 DP 는 모두 연산하게 된다.)

---

코드

@github 에서 확인하기

/**
 * @site: https://www.acmicpc.net/problem/9095
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 07. 19
 */
#include <iostream>
using namespace std;
// 일반적인 방법
int main() {
    int DP[11];
    int i, n, T;
    DP[0] = 1;
    DP[1] = 1;
    DP[2] = 2;
    cin >> T;
    while ((T--)) {
        cin >> n;
        for (i = 3; i <= n; i++) {
            DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3];
        }
        cout << DP[n] << endl;
    }
    return 0;
}
// 중복 계산을 피하기 위해
// 미리 DP 연산을 끝냄
int main() {
    int DP[11];
    int i, n, T;
    DP[0] = 1;
    DP[1] = 1;
    DP[2] = 2;
    cin >> T;
    for (i = 3; i <= 11; i++) {
        DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3];
    }
    while ((T--)) {
        cin >> n;
        cout << DP[n] << endl;
    }
    return 0;
}