[Java] 백준 1904 : 01타일

문제 링크

1.

기본적인 피보나치 수열.

 

 

2.

$N=3,4,5$ 정도까지 직접 써보면 피보나치 수열을 이룬다는 것을 쉽게 알 수 있다.

 

개수를 15746으로 나눈 나머지로 저장한다는 문제 조건을 잊으면 안 된다.

 

사실 처음에는 재귀 함수를 사용해서 풀어봤는데, 스택 오버플로우가 발생하였다.

N이 최대 백만이니 재귀는 비효율적이라는 것을 알 수 있다.

 

3.

import java.util.Scanner;

public class Main {
	static int[] dp;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		dp = new int[n + 1];

		if (n >= 1) {
			dp[1] = 1;
		}
		if (n >= 2) {
			dp[2] = 2;
		}
		if (n >= 3) {
			for (int i = 3; i <= n; i++) {
				dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
			}
		}

		System.out.println(dp[n] % 15746);
		sc.close();
	}
}

 

 

4.

none