1, 2, 3 더하기

문제

1, 2, 3 더하기

풀이

를 의 합으로 나타내는 방법의 수를 라고 합시다. 는 , , 으로 나타낼 수 있습니다. 따라서 아래 점화식을 통해 답을 구할 수 있습니다.

코드

Python

dp = [0] * 11
dp[1] = 1
dp[2] = 1 + dp[1]
dp[3] = 1 + dp[2] + dp[1]
 
for i in range(4, 11):
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
 
for _ in range(int(input())):
    print(dp[int(input())])

C++

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    array<int, 11> dp = {};
    dp[1] = 1;
    dp[2] = 1 + dp[1];
    dp[3] = 1 + dp[2] + dp[1];
 
    for (int i = 4; i < 11; i++)
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << dp[n] << '\n';
    }
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int dp[] = new int[11];
        dp[1] = 1;
        dp[2] = 1 + dp[1];
        dp[3] = 1 + dp[2] + dp[1];
 
        for (int i = 4; i < 11; i++)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
 
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n] + "\n");
        }
 
        bw.close();
    }
}