99클럽 코테 스터디 29일차 TIL

백준 - 9461번

파도반 수열이라 하니 비슷한 피포나치 수열이 생각난다. 억지

피보나치수열에는 패턴이 존재하는데, 파도반 수열 문제에 나열된 숫자들도 어떤 패턴을 가지고 있을 것 같다.

 

피보나치 수열

N = 10 조건을 가지는 피보나치수열을 구한다면 1 + 1 + 2 + 3 + 5 + 8 + 13 + 22 + 35 + 55이다.

F(1) = F(2) = 1의 초기값을 가지며 점화식으로 F(n) = F(n-1) + F(n-2)가 된다.

 

파도반 수열

먼저 변의 길이는 생각하지 말고(?) 규칙을 찾기 위한 삼각형을 그려보자.

여러 방식으로 그림을 그려봤지만 이 그림에서 규칙을 찾게 되었다.

문제의 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 수열에서 보면 4번 삼각형을 그렸을 때 변의 길이가 늘어나기 시작하고,

6번 삼각형을 그릴 때부터 패턴을 가지는 것을 볼 수 있다.

 

6번 삼각형이 만들어지기 위해 1번과 5번, 

7번 삼각형이 만들어지기 위해 2번과 6번...

이 규칙을 공식화해 보면 P(6) = P(6 - 1) + P(6 - 5) / P(7) = P(7 - 1) + P(7 - 5)

즉, F(n) = F(n-1) + F(n-5)가 된다.

하지만 위 공식을 사용하려면 4번 삼각형까지 초기값을 가져야 한다.

문제에서 초기값을 가질 수 있는 삼각형은 3번 삼각형까지다.

 

특정 삼각형 변의 길이를 구하기 위해 평행선을 긋고 평행사변형을 만들어보며 공식을 구하는 방법도 있다.

위 방법을 사용했을 때 F(n) = F(n-2) + F(n-3) 공식이 성립된다.

내 그림은 너무 난잡해서 올리질 못하겠다..

 

구현

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());

            long result = padovan(N);

            sb.append(result).append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    private static long padovan(int N) {
        if (N < 4) {
            return 1;
        }

        long[] arr = new long[N + 1];
        
        // 3번 삼각형까지 초기값 설정
        arr[1] = arr[2] = arr[3] = 1;
        for (int i = 4; i <= N; i++) {
            arr[i] = arr[i-2] + arr[i-3];
        }
        return arr[N];
    }
}

---

백준 9461번 - 파도반 수열

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