BOJ 9095 | 1, 2, 3 더하기

🔍 미리보기 이미지

🔗 문제 링크

문제 스택	문제 번호	언어
BOJ	9095	C99

🔑 풀이

그림판이 아닌 draw.io로 그린 것.

음, 이것도 역시 DP 문제인데, 그림을 하나씩 설명하자니, 설명이 더러워질 것 같고.

생각보다 직관적이여서, 조금만 쳐다보고 있으면 이해 될 것이다!

mem[i] = mem[i - 3] + mem[i - 2] + mem[i - 1];

나중에 DP문제를 충분히 많이 풀고 나면,

어떤 문제들이 점화식으로 모델링 할 수 있는지와

이 문제는 어떤 점에서 DP로 풀어야 하는가(?)

정도를 추가하면 좋을 것 같다.

📝 코드

#include <stdio.h>

int	mem[16];

int main(void)
{
  int		count;
  int		x;
  int		i;

  mem[1] = 1;
  mem[2] = 2;
  mem[3] = 4;
  i = 3;
  while (++i < 11)
      mem[i] = mem[i - 3] + mem[i - 2] + mem[i - 1];
  scanf("%d", &count);
  while(count--)
  {
      scanf("%d", &x);
      printf("%d\n", mem[x]);
  }
  return (0);
}