[백준 9095] 1,2,3 더하기

1,2,3 더하기

문제설명

테스트 케이스 수를 입력 받고, 구하고자 하는 수를 입력 받은 뒤 그 정수를 1,2,3의 합으로 나타내는 총 방법의 수를 출력하라.
그리고 그 동작을 테스트 케이스 수만큼 반복한다.

알고리즘

1. 테스트케이스와 구하고자 하는 수를 입력 받는다.
2. 초기값을 저장한다.
3. 연산에 필요한 만큼 반복문을 통해서 미리 계산한다.
4. 값을 조회하여 알맞은 부분을 출력시킨다.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

int main(void)
{
    int T;
    cin >> T;//테스트 케이스 수 입력
    while (T)
    {
        int N;//계산하고자 하는 수 입력 
        int dp[12];
        cin >> N;
        //초기값 
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 4;

        for (int i = 3; i < 12; i++)//연산
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];

        cout << dp[N - 1] << "\n";//출력
        T--;
    }

    return 0;
}

과정

위의 문제는 다이나믹 프로그래밍 문제이기 때문에 bottom-up 또는 top-down방식을 사용해서 풀어야한다.
이번 문제에서는 bottom-up: 아래부터 차례로 확인하는 방식으로 구할 수 있었다.
각 정수별로 직접 몇 가지 인지 세어보고 규칙을 찾아서 풀 수 있었다.
시간 감소를 위해서 연산이 된 것들은 배열안에 저장하고 다시 사용하는 방식이다.
규칙을 구해보니 dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]와 같이 전의 3가지 값을 더하면 다음 값이 나오는 것을 확인할 수 있다.

고찰

단순한 dp문제여서 해결할 수 있었던 것 같다. 다른 유형들도 좀 더 풀어서 개념을 잡을 필요가 있을 것 같다.