SSAFY 알고리즘 수업 오늘의 주제는 dp다.
DP
는 차근차근 과정을 들으면 알 것 같은데 다시보면 어렵다.
아래 두개의 문제는 DP
기본 개념을 연습해볼 수 있는 문제이다.
자세한 내용 정리는 다음에..
아파트를 각 층별로 파란색 또는 노란색 페인트로 칠하되 다음과 같은 규칙으로 칠하려고 한다.
이와 같은 규칙으로 층의 아파트를 칠할 수 있는 방법의 수를 f(n)이라 하면 다음과 같이
f(1) = 2
, f(2) = 3
이다. f(8)은 얼마인가?
N단계에 노란색
이 오는 경우 : N-1단계의 경우의 수를 가진다. -> f(N-1)
N단계에 파란색
이 오는 경우 : N-1단계에 노란색
이 오는 경우의 수와 같다. -> f(N-2)
f(1) = 2, f(2) = 3;
f(n) = f(n-1) + f(n-2);
f(8) =
f(7) + f(6) = 34
1cm
짜리 파란 막대
와 1cm
짜리 노란 막대
그리고 2cm
짜리 빨간 막대
가 있다.
이 막대들을 연결하여 길이가 Ncm인 막대를 만드는 방법의 수를 f(n)이라 하자.
예를 들면 2cm 막대를 만드는 방법은
파란 막대
파란 막대
파란 막대
노란 막대
노란 막대
파란 막대
노란 막대
노란 막대
빨간 막대
f(2) = 5
이다. f(6)의 값은?f(n)은 f(n-1)에서 연결하는 방법(노란색/파란색)과 f(n-2)에서 연결하는 방법(빨간색)이 있다.
그러므로
f(n) = f(n-1)*2 + f(n-2)
f(2) = 3;
f(6) =
f(5)*2 + f(4) = 70