[BOJ] 9095 1, 2, 3 더하기

🙂 문제 분석 및 프로그램 설계

2xn 타일링과 비슷한 문제이다. 숫자가 주어지면 그 숫자를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 구하는 방법이다. 이것도 dp문제이고 전 문제와 매우 유사하다.

💻 소스코드

#include <iostream>
#include <array>
using namespace std;

int main() {
    int T;
    cin >> T;

    array<int, 11> arr;

    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 4;

    for (int n = 3; n < 11; n++) {
        int k = n-1;
        int l = k-1;
        int m = l-1;

        arr[n] = arr[k] + arr[l] + arr[m];
    }

    while (T--) {
        int N;
        cin >> N;
        N--;
        cout << arr[N] << endl;

    }
}

😊 문제를 풀기 위해 생각하고 해결했던 과정 및 느낀점

2xn 타일링 문제는 마지막 타일의 경우를 구하였다. 이것도 비슷하다. 마지막에 더할 수가 무엇인지 경우를 나누고 경우의 수를 계산하면 된다.
마지막에 1을 더하면 남은 수는 n-1을 1, 2, 3을 이용하여 나타낼 경우, 마지막에 2를 더하면 n-2를, 마지막에 3을 더하면 n-3을 나타낼 경우를 생각하면 된다. 즉 n을 나타낼 경우는 n-1, n-2, n-3을 나타낼 경우들의 합이다.
N의 범위가 작으므로 배열을 만들어서 각각 경우의 수를 계산하여 대입하고 출력을 해줬다.