[boj] (s3) 9095 1,2,3 더하기

20770 단어 bojboj

✅ DP

문제

링크

1. 문제 접근 및 해결 로직

구성 숫자가 같아도 순서가 다른 것은 다른 조합으로 친다.
따라서 f(n)f(n)을 정수 nn 을 1,2,3의 합으로 나타내는 방법의 수라고 하고
몇가지를 구해보면
f(1)=1f(1)=1

{1}

f(2)=2f(2)=2

{1,1}
{2}

f(3)=4f(3)=4

{1,1,1}
{1,2}
{2,1}
{3}

f(4)=7f(4)=7

{1,1,1,1}
{1,2,1}
{2,1,1}
{1,1,2}
{3,1}
{1,3}
{2,2}

여기서 다음과 같은 규칙을 발견할 수 있다.
f(4)=f(3)+f(2)+f(1)=4+2+1=7f(4)=f(3)+f(2)+f(1)=4+2+1=7

따라서 점화식은
f(n)=f(n1)+f(n2)+f(n3)f(n)=f(n-1)+f(n-2)+f(n-3)

의사코드

  • 정의
    f(n)f(n) : 정수 nn 을 1,2,3의 합으로 나타내는 방법의 수
  • 구하는 답
    f(n)f(n)
  • 초기값
    f(1)=1f(1)=1
  • 점화식
    f(n)=f(n1)+f(n2)+f(n3),(n>3)f(n)=f(n-1)+f(n-2)+f(n-3),(n>3)

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
O(N)O(N)

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항

좋은 웹페이지 즐겨찾기