2839: 설탕배달

#include <stdio.h>

int arr[5001];// global 변수라서 자동으로 0으로 초기화됨
//Dynamic Programming(큰걸 작은걸로)
int main(void)
{
 int n;
  scanf("%d",&n);

  arr[3]=arr[5]=1;

  for(int i=6;i<=n;i++)
    {
      if(arr[i-3]!=0)
        arr[i]=arr[i-3]+1;
      if(arr[i-5]!=0) //arr[i-3]이 먼저 계산되어 ,arr[,i] 값이 두개 될 수 있음
      {
        if(arr[i-3]!=0)
          arr[i]=arr[i]<arr[i-5]+1? arr[i]:arr[i-5]+1; //arr[i]가 업데이트
        else
          arr[i]=arr[i-5]+1; //업데이트X
      }
        
    }
  if(arr[n]==0)
    printf("-1");
  else
    printf("%d",arr[n]);
  return 0;
}

 

 

#include <stdio.h>
#include <math.h>


int main(void)
{
 int n;
  scanf("%d",&n);
int five,three;
  five=n/5; //5로 나눈 몫
  three=n/3; //3으로 나눈 몫
  int de=0,cnt=0;// 0이면 정확히 n그램 못만듦, 1이면 정확히 만들 수 있음
  int arr[2][5000]; //윗줄은 i를 아랫줄은 j를
  for(int i=0;i<=five;i++)
    {
      
      for(int j=0; j<=three;j++)
        {
          int cpy=n;
          if(cpy==5*i+3*j)
          {
            de=1;
            arr[0][cnt]=i;
            arr[1][cnt++]=j;
            
          }
        }
    }
  if(de==0)
  {
     printf("-1");
   /* if(five==0 && n%3==0)
      printf("%d",three);
    else
      printf("-1");*/
  }
    
  else
  {
    int min=5000;
    for(int i=0;i<cnt;i++)
      {
        if(min>arr[0][i]+arr[1][i])
          min=arr[0][i]+arr[1][i];
      }
    printf("%d", min);
  }
  
  return 0;
}