문제 출처

단계별로 풀어보기 > 동적 계획법1 > 파도반 수열
https://www.acmicpc.net/problem/9461

문제 설명

접근 방법

import java.io.*;

public class 파도반_수열 {
    public static long dp[] = new long[101];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

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

        for(int i = 4; i < 101; i++) {
            dp[i] = dp[i-2] + dp[i-3];
        }

        for(int i = 0; i < T; i++){
            sb.append(dp[Integer.parseInt(br.readLine())]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

처음 풀 땐, 규칙이 5개 뒤와 1개 뒤 인줄 알았다. 그림을 보고 이해했기 때문에 그런 결과가 나왔으나 숫자를 다시 순차적으로 나열하니 2,3 번째 뒤의 합이였다.

시간 복잡도는 100개의 dp를 채우는 것 이외에는 테스트케이스 반복 밖에 없으므로 O(T)이다.

문제푼 흔적