다이나믹 프로래밍

1. 다이나믹 프로그래밍

큰 문제를 작은 문제로 나눠서  푸는 방법

작은 문제를 해결하고 해결한 결과를 저장함으로써 큰 문제를 계산할 때 연산 횟수를 줄인다.

이 때 n번째 값에 대응될 수 있는 $a_{i}$의 점화식을 찾아내는것이 다이나믹 프로그래밍의 핵심이다. 

 

2. 2×n 타일링 (백준 11726번)

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

문제:

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력:

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력:

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

Solution:

대표적인 다이나믹 프로그래밍 문제이다.

여기서 10,007이라는 수는 단순히 큰 수를 줄이기 위한 숫자로 특수한 의미를 갖고있지 않다.

가로의 길이가 $n$일 때 타일의 갯수를 구하는 방법은 다음과 같이 생각해 볼 수 있다.

즉,

$$(가로의 길이가 n일 때 경우의 수)=  (n-1일 때의 경우의 수)+ (n-2일 때의 경우의 수)$$

따라서 다음과 같이 점화식을 세울 수 있다. 여기서 $a_{i}$는 가로의 길이가 n일 때 경우의 수이다.

$$ a_{i}= a_{i-1}+ a_{i-2}$$

따라서 다음과 같이 풀 수 있다.

 

소스코드:

github.com/mooooondh/baekjoon/tree/master/11726

mooooondh/baekjoon

 

#################################

잘못된 내용 발견시 덧글 부탁드립니다. 
#################################