[코드트리] 숫자 암호 만들기

문제 링크

문제

1,2,3,4 를 가지고 입력된 숫자를 만드는 경우의 수 구하기
예를 들어 4의 경우
1 1 1 1
1 1 2
2 1 1
1 2 1
1 3
3 1
2 2
4

이렇게 8개를 만든다

문제풀이

package java_algo;

import java.util.*;

public class dp {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();

        int[] dp = new int[n + 1]; // 합
        
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        // {1, 2, 3, 4}
        for (int i = 3; i <= n; i++){
            if (i == 3)
                dp[3] = dp[2] + dp[1] + dp[0];
            else
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4];
        }
        System.out.println(dp[n]);
    }
}

설명

1,2,3,4로 암호를 만들어야하기 때문에
지금 수(i)의 총 합을 알기 위해서는 이전 i-1, i-2, i-3, i-4의 개수의 합이 필요하다.
각각에서 1,2,3,4씩 더해주면 i가 되기 때문에