Backjoon(백준) 9641번 - 파도반 수열(Java)

*풀이과정

 - 주어진 나선형에서 케이스를 더 그려본다

 - 반복되는 케이스에서 삼각형이 어떤식으로 만들어지는지 규칙을 파악한다.

 - 규칙을 점화식으로 도출하고 코드로 옮긴다.

 - 코드로 옮기는 과정에서는 메모이제이션 기법 또는 DP문제를 풀때 적용하는 기법을 사용하여 코드를 작성한다.

 

*규칙

 - n이 6이상일 때 부터 n번째 삼각형은 n-1번째 삼각형과 n-5번째 변의 삼각형의 합이다.

 - 따라서 n = (n-1) + (n-5) 라는 점화식을 도출할 수 있다.

 

 

import java.util.Scanner;

// 9461 파도반수열
public class Padovan {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        long[] arr = new long[101];
        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;
        arr[4] = 2;
        arr[5] = 2;
        
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int n = sc.nextInt();
            long result = 0;
            if (n == 1 || n == 2 || n == 3) {
                result = 1;
            }
            else if (n == 4 || n == 5) {
                result = 2;
            } else {
                for (int i = 6; i <= n; i++) {
                    arr[i] = arr[i - 1] + arr[i - 5];
                }
                result = arr[n];
            }
            
            System.out.println(result);
        }

    }

}

 

 

 

 

 

 

 

* 다른 풀이

( https://zorba91.tistory.com/157 ) 참고해서 풀어보기