Kangho_Story

알고리즘 분류DP문제 설명2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.입력 설명첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력 설명첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.예제 입력2 9예제 출력2 55아이디어n이 1일 때 1가지n이 2일 때 2가지n이 3일 때 3가지n이 4일 때 5가지...n이 9일 때 55가지 이것을 보고 피보나치수열임을 알았다.알고리즘DP를 사용해서 기존에 이미 계산했던 값은 벡터에 저장해두어 중복 계산을 방지하며 재귀로 푼다.또한 10007로 나눈 나머지를 저장하고 리턴하는 것도 잊지 말자.코드#inc..