띠그랭

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

#define n 101

long long dp[n] = { 0,1,1,1,2,2 };

void podo()

{

for (int i = 6; i <= 100; i++)

{

dp[i] = dp[i - 5] + dp[i - 1];   //  <-- 파도반 수열의 엔진

}

}

int main()

{

podo();

int arr[100] = { 0 };

int test;

scanf("%d",&test);

for (int i = 1; i <= test; i++)

scanf("%d",&arr[i]);

for (int i = 1; i <= test; i++)

printf("%lld\n",dp[arr[i]]);

return 0;

}

파도반 수열은 규칙이 딱 있다. 

dp[i] = dp [i - 5] + dp[i - 1]

예를 들어서  8번째 파도반 수열의 수를 구한다면  3번째 수 + 7번째 수를 더해주면 된다,

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

#define N 1000000

int dp[N];

void fibo(int n)

{

for (int i = 2; i <= n; i++)

{

dp[i] = dp[i - 1] + 1;                                    

if (i % 2 == 0)

{

if (dp[i] > dp[i / 2] + 1)

dp[i] = dp[i / 2] + 1;

}

if (i % 3 == 0)

{

if (dp[i] > dp[i / 3] + 1)

dp[i] = dp[i / 3] + 1;

}

}

}

int main()

{

    int a;

    scanf("%d",&a);

fibo(a);

    printf("%d",dp[a]);

}

DP 에서 bottom - up 으로 풀었다.

DP는 배열에다 메모이제이션하는 방법으로 동일한 방법의 계산을 반복할때, 이전의 값들을 저장하는 방법인데

이 문제를 보면 

입력이 주어졌을때 위의 세가지 규칙들을 이용하여  입력된 수를 1로 최소한의 횟수로 만드는 문제

1에서 1로 만들때 드는 횟수는 당연히 0번   ---> 배열1에는 0삽입

1에서 2로 만들때 드는 방법은 2가지가 있다. 1에서 +1 하는 경우 or 1에서 x2하는 경우  하지만 둘다 횟수 1번으로 동일하기 때문에 --> 배열2에는 1삽입 

1에서 3으로 만들때 드는 방법은 2가지 -->  1에서 x3 하는 경우  or  2에서 +1 하는 경우 ,     이때 1에서 x3 하는 경우는 횟수가 1번이지만 ,  2에서 +1 하는 경우는 횟수가 2번이다.  왜냐하면  1에서 2로 갈때 벌써 횟수1번을 소모했으니 2에서 3으로갈때 총 횟수가 2번이다   

그래서  3으로 만들때 드는 가장 최소한의 횟수는 1번이다.(1에서 x3한 방법)

만약 입력이 11이라면 배열은 요로코롬 만들어질것.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

int main()

{

int n;

long long dp[91] = { 0,1 };      // <-- 자료형 만 변경

scanf("%d",&n);

for (int i = 2; i <= n; i++)

dp[i] = dp[i - 2] + dp[i - 1];         // <-- 1번 문제와 엔진 동일

printf("%lld",dp[n]);       // <-- long long이므로 lld를 써줌

return 0;

}

피보나치 수열 1번문제랑 다른점은 입력 n의 범위가 90까지 늘어난것..

int로는 표현할수 있는 수를 넘어가기 때문에  어마무시하게 긴 long long을 썼다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

int main()

{

int n;

int dp[46] = { 0,1 };        //입력 n이 45까지 가능하므로 배열은 46까지 ,, 그냥 넉넉하게 배열을 만들어줘도됨

scanf("%d",&n);

for (int i = 2; i <= n; i++)

dp[i] = dp[i - 2] + dp[i - 1];      //  <----  피보나치 문제의 엔진    

printf("%d",dp[n]);

return 0;

}