점화식 세우는 팁
1. 역으로 생각하기
연습문제 1.
문제 노란색은 인접한 두 층에 연속해서 사용 가능, 파란색은 불가하다고 하자. n층짜리 건물을 이 규칙에 따라 칠하는 방법의 수를 f(n)이라고 하면, f(8)의 값은? 예시 1층 건물은 노랑/파랑 상관없으므로, f(1)=2이며, 2층 건물은 2층/1층 이라고 할때 노/노 파/노 노/파 이므로 f(2)=3이다.
풀이 ‘최상층’ 부터 생각해본다. n층이 최상층일떄, y(n)을 n층에 노란색을 칠한 경우라고 하고, b(n)을 n층에 파란색을 칠한 경우라고 하자.
이제 생각한다.
f(n)은 , 노란색이 최상층이거나 파란색이 최상층인 경우이다. 즉 f(n) = y(n) + b(n)
노란색이 최상층인 경우를 생각해보면, 바로 밑 층은 노란색/파란색 관계없다. y(n) = f(n-1)
하지만, 파란색이 최상층이면, 바로 밑 층은 반드시 최상층이 노란색 층인 경우만 가능하다. b(n) = y(n-1). 이때, y(n) = f(n-1) 이므로, b(n) = y(n-1) = f(n-2)이다. 따라서, b(n) = f(n-2)
점화식이 나왔다. f(n) = y(n) + b(n) = f(n-1) + f(n-2) 이므로,
f(n) = f(n-1) + f(n-2)
경우의 수를 분류하기
연습문제 2.
문제 파란막대는 1cm, 노란막대도 1cm, 빨간막대는 2cm이다. 순서대로 이어붙여서 n cm인 막대를 만드는 방법의 수를 f(n)이라 하자. f(6)은 얼마인가? 예시 f(1) = 2 (파 or 노) 이며, f(2) = 5 (파파 파노 노파 노노 빨) 이다.
풀이 순서
- f(n)을 정의
- n cm를 칠할 때 마지막 칠할 수 있는 경우의 수를 분류
- 분류한 각각의 경우에 대해 점화식 유도
- 각 점화식을 합치기
- f(n) = 길이 n 막대 만드는 경우의 수
- 분류
- 마지막을 파란색으로 끝내기 = b(n)
- n-1cm까지 완성된 막대에 파란 막대(1cm)를 붙인다. b(n) = f(n-1)
- 마지막을 노란색으로 끝내기 = y(n)
- n-1cm까지 완성된 막대에 노란 막대(1cm)를 붙인다. y(n) = f(n-1)
- 마지막을 빨강색으로 끝내기 = r(n)
- n-2cm까지 완성된 막대에 빨간 막대(2cm)를 붙인다. r(n) = f(n-2)
- 유도
- f(n) = b(n) + y(n) + r(n) = f(n-1) + f(n-1) + f(n-2)
- f(n) = f(n-1) x 2 + f(n-2)
- dp[i] = dp[i-1] * 2 + dp[i-2]
연습문제 3.
문제 파란막대는 1cm, 노란막대도 1cm, 빨간막대는 2cm이다. 순서대로 이어붙여서 n cm인 막대를 만드는 방법의 수를 f(n)이라 하자. 단, 빨간막대는 연속으로 칠할 수 없다. f(6)은 얼마인가? 예시 f(1) = 2 (파 or 노) 이며, f(2) = 5 (파파 파노 노파 노노 빨) 이다.
풀이 순서
- f(n)을 정의
- n cm를 칠할 때 마지막 칠할 수 있는 경우의 수를 분류
- 분류한 각각의 경우에 대해 점화식 유도
- 각 점화식을 합치기
- f(n) = 길이 n 막대 만드는 경우의 수
- 분류
- 마지막을 파란색으로 끝내기 = b(n)
- n-1cm까지 완성된 막대에 파란 막대(1cm)를 붙인다. b(n) = f(n-1)
- 마지막을 노란색으로 끝내기 = y(n)
- n-1cm까지 완성된 막대에 노란 막대(1cm)를 붙인다. y(n) = f(n-1)
- 마지막을 빨강색으로 끝내기 = r(n)
- n-2cm까지 완성된 막대가 파란색이거나 노란색일 때, 빨간 막대(2cm)를 붙인다. **r(n) = b(n-2) + y(n-2) **
- 유도
- f(n) = b(n) + y(n) + r(n) = f(n-1) + f(n-3) + f(n-3)
- f(n) = f(n-3) x 2 + f(n-2)
- dp[i] = dp[i-3] * 2 + dp[i-2]