[C] 9095: 1, 2, 3 더하기

이 문제 역시 Dynamic Programming을 이용한 문제이다.

 

Dynamic Programming의 특징은 첫째로 문제를 작게 나누어 최대한 연산을 반복하지 않도록 하는 것이고

 

둘째로는 배열에 값을 저장하여 점화식을 이용하여 푸는 문제가 많은 것이다.

 

이 문제 역시 점화식만 잘 알 수 있었다면 쉽게 풀 수 있다.

 

예를 들어 4의 경우

4=1+3, 2+2, 1+3 이런식으로 표현할 수 있는데

1+3은 1+cpy[3], 2+2=2+cpy[2], 1+3=cpy[3] 으로 생각하면

4를 1,2,3으로 표현하는 모든 경우의 수를 표현할 수 있다.

 

이를 일반화 하면 cpy[i]=cpy[i-1]+cpy[i-2]+cpy[i-3]으로 표현할 수 있고

max를 구한 이유는 물론 이 문제는 10까지만 표현하면 되므로 굳이 할 필요는 없지만

입력 받은 정수가 너무 커지면 불필요한 연산을 하지 않기 위해 넣어둔 것이다.

 

1#include <stdio.h>

int main(void)
{
  int n;
  scanf("%d",&n);
  int arr[n];
  int max=0;
  for(int i=0;i<n;i++)
    {
      scanf("%d",&arr[i]);
      max=arr[i]>max?arr[i]:max; //max까지만 수를 계산함
    }
  int cpy[max+1]; //저장할 배열
  cpy[1]=1;
  cpy[2]=2;
  cpy[3]=4;
  for(int j=4;j<=max;j++)
    {
      cpy[j]=cpy[j-1]+cpy[j-2]+cpy[j-3]; // 점화식을 구하는 것이 중요
    }
  

for(int i=0;i<n;i++)
  {
    printf("%d\n",cpy[arr[i]]);
  }
  

   
  
}