[Java] SWEA 3376번 파도반 수열

SW Expert Academy

---

풀이

예제의 1, 1, 1, 2, 2, 3, 4, 5, 7, 9를 잘 보면 a[i] (i > 3) = a[i - 2] + a[i - 3] 이라는 식을 만들 수 있습니다.

위의 식을 이용해 미리 배열에 결과를 구하고 해당 인덱스를 출력하는 식으로 해결했습니다.

이때, n = 100인 경우 결과 값이 888855064897 이므로 int형의 범위를 훨씬 뛰어넘게 됩니다.

때문에 int 형이 아닌 long 형으로 처리를 해야합니다.

---

코드

import java.util.Scanner;

public class Solution {
	public static long[] arr = new long[101];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; ++tc) {
			int n = sc.nextInt();
			
			arr[1] = 1l;
			arr[2] = 1l;
			arr[3] = 1l;
			
			for (int i = 4; i <= 100; ++i) {
				arr[i] = arr[i - 2] + arr[i - 3];
			}
			
			System.out.println("#" + tc + " " + arr[n]);
		}
		
		sc.close();
	}
}

---

pyo7410/Algorithm