https://www.acmicpc.net/problem/14495

시행착오 1

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Integer n = scanner.nextInt();
		int[] f = new int[n];
		f[0] = f[1] = f[2] = 1;
		for (int i = 3; i < n; i++) {
			f[i] = f[i - 1] + f[i - 3];
		}
		System.out.println(f[n - 1]);
	}
}

그렇다. n의 크기가 1 ~ 3인 경우 위 코드는 index out of range가 된다.

시행착오 2

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Integer n = scanner.nextInt();
		int[] f = new int[n];
		if (n <= 3) {
			System.out.println(1);
			return;
		}
		f[0] = f[1] = f[2] = 1;
		for (int i = 3; i < n; i++) {
			f[i] = f[i - 1] + f[i - 3];
		}
		System.out.println(f[n - 1]);
		scanner.close();
	}
}

n의 범위가 1 ~ 116 까지로, 116번째 피보나치 값이 int 최대값인 2,147,483,647을 넘어가 overflow가 발생한다. 고로 int 대신 long을 사용하도록 하자.

최종

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Integer n = scanner.nextInt();
		int[] f = new int[n + 1];
		f[1] = 1;
		if (n > 1) f[2] = 1;
		if (n > 2) f[3] = 1;
		for (int i = 4; i <= n; i++) {
			f[i] = f[i - 1] + f[i - 3];
		}
		System.out.println(f[n]);
		scanner.close();
	}
}