128. 9461 (파도반 수열)

import java.util.*;
import java.io.*;
import java.math.BigInteger;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();

		int T = sc.nextInt();

		BigInteger[] arr = new BigInteger[1001];

		for (int i = 0; i < T; i++) {
			arr[1] = BigInteger.valueOf(1);
			arr[2] = BigInteger.valueOf(1);
			arr[3] = BigInteger.valueOf(1);
			
			int N = sc.nextInt();

			for (int j = 4; j <= N; j++) {
				arr[j] = arr[j - 2].add(arr[j - 3]);
			}
			
			sb.append(arr[N] + "\n");
		}
		System.out.print(sb);
	}

}

문제요약

작은삼각형이 나선형으로 커지는데 입력값에 따른 삼각형의 개수를 구하시오.

설명

매우 쉬운문제이다.

P(N)에 따른 개수는 다음과 같으며, 3까지는 1로 그 이후에는 P(N) - 2 + P(N) - 3 의 피보나치형태를 띄운다.

 

따라서 

	arr[j] = arr[j - 2].add(arr[j - 3]);

이 로직을 통해 쉽게 구할 수 있다.

주의점

int형은 범위를 초과하기 때문에 큰 수가 들어오면 쓰레기 값이 출력된다.

따라서 범위가 무한대인 BIgInteger를 사용하였다.

 

 

N에따른 결과를 바로 출력하기 위해 arr[0]은 비워 두었으며, 메모리 공간을 아끼고 싶다면

-1씩 붙여주면 된다.