백준 9461번

9461번: 파도반 수열

삼각형이 나선 모양으로 놓아져 있고 나선 에사 가장 긴 변의 길이를 가지고 새로운 정삼각형을 추가하는 문제이다.

예시의 수열을 보면 {1, 1, 1, 2, 2, 3, 4, 5, 7, 9}의 수열이 있다. 

 

점화식을 찾기위해 수열의 값들과 삼각형이 놓이는 일정한 규칙을 찾고자 했다.

사이즈가 12인 삼각형을 예로 들면 12가 놓이기 전에 가장 큰 삼각형이었던 9와 9가 놓이기 4번째 전이였던 삼각형 3을 이용해 12가 만들어졌다.

 

삼각형 9를 이용해 한 번 더 확인하면 9가 생기기 전에 가장 큰 숫자였던 7과 7이 생기기 4번째 전이였던 삼각형 2를 이용해 만들어진 것을 확인할 수 있다.

 

점화식은 다음과 같다

dp [n] = dp [n-1] + dp [i-5]

 

코드

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] testCase = new int[n+1];
        long[] dp = new long[101];

        for(int i = 1; i<=n;++i)
        {
            testCase[i] = sc.nextInt();
        }

        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;

        for(int i = 5;i<=100;++i)
        {
            dp[i] = dp[i-1]+dp[i-5];
        }

        for(int i = 1; i<=n;++i)
        {
            System.out.println(dp[testCase[i]]);
        }

    }

}