DP > 1, 2, 3 더하기 (9095번)

문제

 

---

풀이 

아 재밌다(?)

당연히 재밌지 풀이 보고 풀었는데..ㅋㅋㅋㅋㅋ

이제 다시 감이 조금 살아는 나고있다!

DP는 같은 답 다시 구하면 안돼 -> 반복문이나 재귀함수로 구하고 구한 값은 배열에 저장해!

그 때 중요한건 뭐다? 점화식 구하기!!

이것만 하면 아직까진 어려운 문제 없었음....점화식 못구해서 문제지만ㅋㅋ

암튼 풀이는 음...

여기서 d[n]은 n을 1, 2, 3으로 나타내는 방법의 수이고, 여기서 아이디어는 수를 표현할 때 마지막 수가 뭐냐는거야

n = ㅇ+ㅇ+ㅇ+ ... + ㅇ + ㅁ

여기서 ㅁ이 뭐냐는 거지!!

ㅁ에 올 수 있는 건 1, 2, 3이잖아?

그럼 d[n] = d[n-1] + 1, d[n-2] + 2, d[n-3] +3 될 수 있겠지? (여기서 맨 뒤의 1, 2, 3은 걍 숫자야)

그럼 d[n]을 표현하는 방식은 d[n-1] + d[n-2] + d[n-3]이겠네~

흐름 ㅇㅋ?

보자마자 딱 오긴했는데 안 보면 아직까진 감이 안와...

목표는 이번주 내로 DP 끝내고 점화식 앵간하면 세울 수 있게 하는거야!

---

코드

 

bottom-up

#include <iostream>
#include <stdio.h>
#define MAX 12

int d[12];

using namespace std;

int main()
{
    ///bottom-up
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int t;
    int n[100];
    int res[100];
    cin>>t;
    
    for(int i=0;i<t;i++)
    {
        cin>>n[i];
    }
    
    d[0]=0;
    d[1]=1;
    d[2]=2;
    d[3]=4;
    
    for(int j=0;j<t;j++)
    {
        for(int i=4;i<=n[j];i++)
        {
            if(d[i]!=0) continue;
            d[i]=d[i-1]+d[i-2]+d[i-3];
        }
    }

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

    return 0;
}

이거는 저기 중첩반복문에서 continue 대신 break를 써서 잠깐 아주 잠!깐! 헤맸다..ㅋㅋㅋ

자꾸 두번쨰 결과부터는 0이 나오더라구..

break를 하면 그냥 계산을 안해버려서 끝났나벼.. 암튼

---

Top-down

#include <iostream>
#include <stdio.h>
#define MAX 12

int d[12];

using namespace std;

int go(int n)
{
    if(d[n]!=0) return d[n];
    d[n]=go(n-1)+go(n-2)+go(n-3);
    return d[n];
}

int main()
{
    ///bottom-up
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int t;
    int n[100];
    int res[100];
    cin>>t;
    
    for(int i=0;i<t;i++)
    {
        cin>>n[i];
    }
    
    d[0]=0;
    d[1]=1;
    d[2]=2;
    d[3]=4;
    
    for(int j=0;j<t;j++)
    {
        printf("%d\n",go(n[j]));
    }

    return 0;
}