자바로 백준 1904 풀기

• 실버 3단계 문제

풀이)

이전의 피보나치 수 2와 거의 동일한 방법이기 때문에 크게 설명할 부분은 없었다.
아무리 중복 연산을 제외하고 시간복잡도는 이론적으로 O(N)이라 하지만 매 재귀마다 조건문을 검사하는 등 오버헤드가 커질 수밖에 없을 것이다. 그래서 반복문으로 푸는 것이 더욱 효율적이긴 하다.

내 코드)

import java.util.Scanner;
 
public class Main {
 
	public static int[] dp = new int[1000001];;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
 
		// -1 로 초기화
		for(int i = 3; i < dp.length; i++) {
			dp[i] = -1;
		}
		
		System.out.println(Tile(N));
		
	}
	
	public static int Tile(int N) {
		
		if(dp[N] == -1) {
			dp[N] = (Tile(N - 1) + Tile((N - 2))) % 15746;
		}
		return dp[N];
	}
 
}