띠그랭

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

#include<stdio.h>

#define N 100001

long long dp[N], MAX= -1000, test, SUM;

long long arr[N];

void sum(int a)

{

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

{

SUM += arr[i];

if (MAX < SUM)

MAX = SUM;

if (SUM <= 0)

SUM = 0;

}

}

int main()

{

scanf("%lld", &test);

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

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

sum(test);

printf("%lld", MAX);

return 0;

}

내가 푼 방법은

10부터 -1까지 쭈루루룩 더하는데 

더하면서 합이 양수면 계속 돌진 음수면 합을 0으로 초기화후 다시 돌진 

예를 들면  10 + (-4) = 6 이다 그러므로 계속 돌진 !    ->  6 + 3 = 9 이므로 계속 돌진한다..  이렇게 쭈루룩  6 까지 계속 돌진하면 합은 21이다

근데 큰일났다.    -35라는 거대한 음수가 튀어나왔다.    더해보니  21 + (-35) =  -14 라는 음수가 나온것이다.  음수는 나쁜것이니까 버려야한다.

그러므로 0이되었고 여기서 중요한게 21이라는 것을 MAX라는 변수에 넣어놔야함 .

다시 12부터 쭈루루룩 더한다.    12 + 21 = 33(최대값)이 나오고 조건문을 통해 MAX에는 33이 대입된다.   그다음  33 + (-1)을 하고 종료된다.

여기서 주의해야하는게 MAX에다 0을 넣으면안됨.

왜냐하면 입력때 모든 수가 음수일 수가 있다.  

요로코롬  -3 -5 -2 -1 -6  이렇게 다섯가지의 숫자가 입력될수 있는데 여기서 출력은  -1이 출력되야하는데,   MAX 에 0을 넣어놨다면  마지막 출력도 0이 나와버림.   그래서 시작할때  입력할수있는 가장 적은 수인 -1000을 미리 넣어놨다.

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

#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;

}