[Algorithm] DP 연습하기

Yeoming·2022년 9월 29일
0

들어가기 전

SSAFY 알고리즘 수업 오늘의 주제는 dp다.
DP는 차근차근 과정을 들으면 알 것 같은데 다시보면 어렵다.
아래 두개의 문제는 DP 기본 개념을 연습해볼 수 있는 문제이다.
자세한 내용 정리는 다음에..

아파트 색칠하기

연습문제 1

아파트를 각 층별로 파란색 또는 노란색 페인트로 칠하되 다음과 같은 규칙으로 칠하려고 한다.

  • 노란색은 인접한 두 층에 연속하여 사용할 수 없다.
  • 파란색은 인접한 두 층에 연속하여 사용할 수 없다.

이와 같은 규칙으로 층의 아파트를 칠할 수 있는 방법의 수를 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


막대 색칠하기

연습문제 2

1cm 짜리 파란 막대1cm 짜리 노란 막대 그리고 2cm 짜리 빨간 막대가 있다.
이 막대들을 연결하여 길이가 Ncm인 막대를 만드는 방법의 수를 f(n)이라 하자.
예를 들면 2cm 막대를 만드는 방법은

  • 파란 막대 파란 막대
  • 파란 막대 노란 막대
  • 노란 막대 파란 막대
  • 노란 막대 노란 막대
  • 빨간 막대
  • 5가지 이므로 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

0개의 댓글