백준 9461 파도반 수열 python, java

문제로 주어진 삼각형 그림이 어려워 보여서 주어진 예시를 보고 점화식을 찾아 해결했다.

📜 문제 바로 가기 : 파도반 수열

제출코드

파이썬

import sys
input = sys.stdin.readline

tc = int(input())
tc_arr = [int(input()) for _ in range(tc)]
MAX = max(tc_arr)

arr = [1] * MAX
for i in range(3, MAX):
    arr[i] = arr[i-2] + arr[i-3]

for n in tc_arr:
    print(arr[n-1])

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(br.readLine());
        int[] tc_arr = new int[tc];

        int MAX = 0;
        for (int i = 0; i < tc; i++) {
            tc_arr[i] = Integer.parseInt(br.readLine());
            MAX = Math.max(tc_arr[i], MAX);
        }

        long[] arr = new long[MAX];
        for (int i = 0; i < MAX; i++) {
            arr[i] = 1;
        }

        for (int i = 3; i < MAX; i++) {
            arr[i] = arr[i-2] + arr[i-3];
        }

        for (int n : tc_arr) {
            System.out.println(arr[n-1]);
        }

    }
}

---

접근방법

음.. 그냥 봤는데 그림이 어려워보인다.
주어진 수열을 보니 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이었고
초기값 1, 1, 1을 제외하고 a[i] = a[i-2] + a[i-3]을 만족하는 것을 알 수 있었다.
피보나치 수열과 상당히 유사한데 어쨌든 메모이제이션을 이용하여 풀면 빠르게 실행시킬 수 있을 것이다!