[SWEA] - 3376. 파도반 수열 (D3)

[문제]

아래 그림과 같이 삼각형이 나선모양으로 늘어서 있는 형태를 생각해보자.

아래 그림과 같이 삼각형이 나선모양으로 늘어서 있는 처음에 이 나선은 한 변의 길이가 1인 정삼각형에서 시작한다.
그리고 현재 만들어진 나선에서 가장 긴 변에 그 변의 길이와 같은 크기의 정삼각형을 추가해 넣는다. 파도반 수열 PN은 나선에 N번째로 추가한 나선의 길이를 의미하는 수열이다.
P1에서 P10까지를 순서대로 나열하면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.
N이 주어질 때 PN을 구하는 프로그램을 작성하라.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 자연수 N(1 ≤ N ≤ 100 )이 주어진다.

[출력]
각 테스트 케이스마다 PN을 출력한다.

문제 풀기

3376. 파도반 수열

 

---

[풀이]

• (i > 3) 일 때, a[i]  = a[i - 2] + a[i - 3] 라는 식을 세울 수 있다.
•  n = 100인 경우 결과 값이 888855064897 이므로 int 형의 범위를 넘기때문에 long 형으로 배열을 선언한다.

import java.util.Scanner;

class Solution {	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		long arr[] = new long[101];
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			int n = sc.nextInt();
			
			arr[1] = 1;
			arr[2] = 1;
			arr[3] = 1;
			
			for(int i=4; i<=100; i++) {
				arr[i] = arr[i-2] + arr[i-3];
			}
			
			System.out.format("#%d %d\n", tc, arr[n]);
		}
		
	}
}