[백준 - 9461번] 파도반 수열 - Java //Wello Horld//

이번에는 BOJ의 9461 번 문제 파도반 수열을 풀어보도록 하자

처음에 변의 길이가 1인 정삼각형부터 시작해서, 변을 이어가며 정삼각형을 그리는 문제이다. 

일단, P(1) = 1, P(2) = 1, ... , P(10) = 9, P(11) = 12 가 되는 것이 그림으로, 예시로, 주어져있다.

입력으로는 테스트케이스 T가 먼저 주어지고, 각각의 테스트 케이스에 P(N) 의 N의 값이 주어진다. 출력으로 각 테스트케이스마다 P(N) 값을 출력해주면 되는 문제이다.

이문제를 풀때, 일단 N = 5 일때 까지는, 예외로 생각하고 문제를 풀었다. N = 6일 때부터 P(N) = P(N - 1) + P(N - 5) 가 되므로, 이를 이용해서 N = 1 부터 N = 100까지의 P[N]의 값을 먼저 구하게 해서, 문제를 풀면 아주 간단하다.

성공한 코드는 아래와 같이 작성했다

import java.io.*;
import java.util.*;

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long[] P = new long[101];
        P[1] = 1; P[2] = 1; P[3] = 1; P[4] = 2; P[5] = 2;
        for(int i = 6; i <= 100; i++){
            P[i] = P[i - 1] + P[i - 5];
        }

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            bw.write(P[N] + "\n");
        }
        

        bw.flush();
        br.close();
        bw.close();
    }
}

 

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