[9095]1,2,3 더하기

문제

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

풀이

다이나믹 프로그래밍으로 풀 수 있었다.

n일때 1,2,3을 더해서 n을 표현하는 방법의 가지수를 d[n]이라고 한다.

마지막에 올 수 있는 숫자는 1, 2, 3 인데 

1이 오면 d[n-1]

2가 오면 d[n-2]

3이 오면 d[n-3] 이 성립된다.

이를 바탕으로 점화식을 세워보면

d[n] = d[n-1] + d[n-2] + d[n-3]

top-down 방식

import java.util.Scanner;
//top-down
public class Main {
    static int[] d = new int[11];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        int[] re = new int[t];
        for(int i=0;i<t;i++) {
            int n = scan.nextInt();
            re[i] = add123(n);
        }
        for(int result:re) System.out.println(result);
        scan.close();
    }
    static int add123(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        if(d[n]>0) return d[n];
        else {
            d[n] = add123(n-1) + add123(n-2) + add123(n-3);
            return d[n];
        }
    }
}

bottom-up 방식

import java.util.Scanner;
//bottom-up
public class Main {
    static int[] d = new int[11];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        int[] re = new int[t];
        for(int i=0;i<t;i++) {
            int n = scan.nextInt();
            d[1] = 1;
            d[2] = 2;
            d[3] = 4;
            if(n<4) {
                re[i] = d[n];
            }else {
                for(int j=4;j<=n;j++) {
                    d[j] = d[j-1] + d[j-2] + d[j-3];
                    re[i] = d[j];
                }
            }
        }
        for(int result:re) System.out.println(result);
        scan.close();
    }
}