[BOJ] 백준 9461 파도반 수열

출처: https://www.acmicpc.net/problem/9461

 Input 

2

6

12

 

 Output 

3

16

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

- 처음 정삼각형의 변의 길이는 1입니다.

- 나선형으로 정삼각형들이 추가되는데,

  나선에서 가장 긴 변의 길이를 k 일 때, 추가되는 정삼각형의 길이는 k 입니다.

P(N) = {1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, ...}

dp[i] = i 번째 정삼각형의 변의 길이라고 했을 때, (i > 6)

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

* dp[1] = dp[2] = dp[3] = 1

   dp[4] = dp[5] = 2

 

시뮬레이션

dp[6] = dp[5] + dp[3] = dp[5] + dp[1] 

          = 2 + 1 = 3

 

 

dp[7] = dp[6] + dp[1] = dp[6] + dp[2]

          = 3 + 1 = 4

 

 

dp[8] = dp[7] + dp[2] = dp[7] + dp[3]

          = 4 + 1 = 5

 

 

dp[9] = dp[8] + dp[4]

          = 5 + 2 = 7

 

 

dp[10] = dp[9] + dp[5]

             = 7 +  2 = 9

 

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
         
        // 1<= N <= 100
        // dp[i]는 인덱스 1부터.
        Long [] dp = new Long[101];
         
        dp[1]=1L; dp[2]=1L; dp[3]=1L;
        dp[4]=2L; dp[5]=2L;
 
        // 어떤 테스트케이스가 있을지 모르기에 모든 수에 대해 할당!
        // 여러 테스트케이스가 존재할 수 있으므로 해당 문제에서는 이게 더 효율적일 것이다.
        for(int i=6 ; i <= 100 ; i++) {
            dp[i] = dp[i-1] + dp[i-5];
        }
         
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
         
        // 테스트 케이스는 인덱스 0부터.
        // 입력!
        int[] testCase = new int[n];
        for(int i=0; i<n; i++) {
            testCase[i] = Integer.parseInt(sc.next());
        }
         
        // 출력!
        for(int i=0; i<n; i++) {
            System.out.println(dp[testCase[i]]);
        }
    }
}