#11726 : 2 x n 타일링

풀이방법

사용된 것:

동적 프로그래밍

 

2022.02.22

피보나치 수열 문제와 비슷한 문제이다.

주어진 숫자가 n일 때 문제의 답을 f(n)이라 하면,

f(n) = f(n-1) + f(n-2) 이다. (단 f(1) = 1, f(2) = 2)

 

이를 재귀함수로 구현하면 시간초과가 발생한다.

1 ≤ n ≤ 1000 이므로, 길이가 1000 이상인 배열에 미리 f(1) ~ f(1000)을 모두 구해 저장해둔 뒤 거기서 값을 꺼내어 출력하면 된다.

 

나는 편의를 위해 길이가 1000이 아닌 1001인 배열을 사용하였다. k번 인덱스의 위치에 f(k)가 저장되게 하기 위해서이다.

 

코드

Java(2022.02.22)

import java.io.*;

public class Main {

	static int[] nums;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		nums = new int[1001];
		
		nums[1] = 1;
		nums[2] = 2;
		
		for(int i = 3; i<1001; i++) {
			nums[i] = (nums[i-1] + nums[i-2])%10007;
		}
		
		int n = Integer.parseInt(br.readLine());
		System.out.print(nums[n]);
	}
	
}