백준 9095 - 1, 2, 3 더하기

문제

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

9095번: 1, 2, 3 더하기

 

풀이

1, 2, 3을 이용해서 더한 후 N을 구하는 문제이다. 마지막에 더해지는 숫자에 따라서 N을 구하는 방법을 알 수 있다.

○ + ○ + ○ +  ...  + ●  = N 이라고 할 때, 마지막 ● 에는 1, 2, 3 세 개가 올 수 있다.

따라서 ●는 N - 1, N - 2, N - 3 중에 하나가 되고, 이 세 가지가 되는 방법의 수를 더하면 결국 N까지 더하는 방법의 수가 만들어 진다.

 

D[N] = N을 1, 2, 3으로 나타내는 경우의 수 라고 하면

D[N] = D[N-1] + D[N-2] + D[N-3] 이 된다.

 

코드

c++

#include <iostream>
 
using namespace std;
 
int T;
int dp[11];
int result;
 
int f(int N)
{
    if (dp[N]) return dp[N];
    return dp[N] = f(N - 1) + f(N - 2) + f(N - 3);
}
 
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> T;
 
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
 
    int N;
    while (T--)
    {
        cin >> N;
        cout << f(N) << '\n';
    }
    return 0;
}

 

java

import java.util.Scanner;
 
public class Main {
 
    static int t, n;
    static Scanner sc = new Scanner(System.in);
    static int[] d = new int[11];
 
    public static void main(String[] args) {
        t = sc.nextInt();
        solve();
        for (int i = 0; i < t; i++) {
            n = sc.nextInt();
            System.out.println(d[n]);
        }
    }
 
    private static void solve() {
        d[1] = 1;
        d[2] = 2;
        d[3] = 4;
 
        for (int i = 4; i <= 10; i++) {
            d[i] = d[i - 1] + d[i - 2] + d[i - 3];
        }
    }
}