백준 9461 - 파도반 수열

깃허브:

https://github.com/MSIQOC/BOJ/blob/master/b9461_%ED%8C%8C%EB%8F%84%EB%B0%98%EC%88%98%EC%97%B4.java

 

www.acmicpc.net/problem/9461

9461번: 파도반 수열

주어진 그림에서 계속해서 나선모양으로 정삼각형을 그려나가며 규칙을 찾아보았다.

1부터 9까지는 기본적으로 주어진 것이고, 그 뒤로 계속 구해보다보면 규칙을 발견하게 된다.

위 그림을 토대로 기본적으로 주어진 것의 다음 숫자에 대해서는 다음과 같은 점화식을 세울 수 있다.

이를 코드로 표현해보면 위와 같이 p[1]부터 p[10]까지는 기본으로 주어진 값을 저장시키고 그 다음부터 p[100]까지는 위에서 구한 점화식을 이용하면 된다.

//
//  Created by MinSeo on 2021/03/27.
//  Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
//
import java.io.*;
import java.util.*;
public class b9461_파도반수열 {
    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());
        long p[] = new long[101];
        p[1] = 1;
        p[2] = 1;
        p[3] = 1;
        p[4] = 2;
        p[5] = 2;
        p[6] = 3;
        p[7] = 4;
        p[8] = 5;
        p[9] = 7;
        p[10] = 9; //초기화
        for(int i=11; i<=100; ++i) {
            p[i] = p[i-1] + p[i-5];
        }
        while(t-- > 0) {
            int a = Integer.parseInt(br.readLine());
            bw.write(p[a] + "\n");
        }
        bw.flush();
    }
}