qhrrkfl2   7년 전

여러가지 케이스를 보고 피보나치수열이다! 라고 알아채신분이 있던데

어떻게 그런 수학적 사실을 이끌어낼수 있었을까요? ㅠㅠ

kesakiyo   7년 전

점화식을 세워보면 그런 사실을 이끌어낼 수 있습니다.

현재 길이가 1, 2인 타일밖에 안가지고 있습니다.


이 때 f(n)을 길이가 n인 타일의 개수라고 정의를 하고 f(n)이 어떻게 계산되나 생각을 해봅시다.

f(n)을 만드는 방법은 총 두가지가 있습니다.

1. f(n - 1)에서 길이가 1인 타일을 붙여서 만든다.

2. f(n - 2)에서 길이가 2인 타일을 붙여서 만든다.


따라서 f(n)의 경우의 수는 f(n - 1) + f(n - 2)가 됩니다.

그렇기 때문에 이 문제는 피보나치랑 같은 문제가 되는겁니다.

qhrrkfl2   7년 전

아하 그렇군요! 이산수학인가요? 저런식으로 도출이 바로바로 되다니 신기하군요

kesakiyo   7년 전

정확히 말하면 Dynamic Programming(동적계획법)이라고 하는게 맞겠네요.

흔히들 줄여서 dp라고 얘기합니다.


dp가 뭔지 간단히 얘기하자면 한 문제를 작은 부분문제들로 쪼개 풀어야 하고

이 작은 부분문제들이 여러번 계산해야 하는 상황이라면 이를 테이블(Array등)에 기록해 중복되는 계산을 하지 않는 기법을 의미합니다.


사실 이 문제는 dp의 입문중의 입문에 속하는 문제입니다. 

프로그래밍으로 치자면 "hello world"를 출력하라 정도가 되겠네요.

인터넷에서 한번 dp를 검색한 뒤 학습해 보고 BOJ에서 여러 문제들을 풀어보세요.

재미있는 경험이 될 것입니다.


답변이 도움이 됐으면 좋겠네요.

qhrrkfl2   7년 전

그렇군요 답변갑사합니다!

댓글을 작성하려면 로그인해야 합니다.