DP > 오르막 수 (11057번)

문제

---

풀이

이것또한!! 2차원배열 기법(?)으로 구현했다ㅎㅎㅎ

아주 재밌고만

막판에 내가 이걸 오르막수라고 같은 수가 중복되면 안될줄 알고 구현했더니 수가 자꾸 모자란겨..

아쒸 왜저래 했는데 알고보니까 이거더라구... 에혀

그치만 재밌당ㅎㅎㅎ 자 풀이 시작!

 

자 이차원배열 d[i][j]는 길이가 i이고, 맨 뒤가 j인 수의 갯수이다.

그리고 d[i][j]는 쪼개면 d[i-1][j-k] 이런식으로 오는데 j-k는 j보다 작거나 같아야 한다.

요기가 약간 헷갈렸는데 오르막수는 진짜 딱 수열이라서 n이 2면 00도 가능하다!

암튼 그래서 얘는 3중 반복문이 필요하고 결과 값은 j가 0부터 9까지 모두 더해주면 된다

(저기 필기에는 1로 되어있지만ㅋㅋㅋ)

이렇게 정리하니까 별로 안어려워 보이지만 엄청 고민 오래했따

이게 생각하다보면 계속 꼬여서 잉?하는 떄가 있는데 그때는 직접 써가면서 풀면 좋은 것같다

이제 아래 코드 봐봐

---

코드

#include <iostream>
#include <stdio.h>
#define MAX 1001
#define mod 10007

long long d[MAX][10];

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    long long res=0;
    cin >> n;
    
    for(int i=0;i<=9;i++)
    {
        d[0][i]=0;
        d[1][i]=1;
    }
    
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=9;j++)
        {
            d[i][j]=0;
            for(int k=0;k<=j;k++)
            {
                d[i][j] += d[i-1][j-k];
                
            }
            d[i][j]%=mod;
        }
    }
    
    for(int i=0;i<=9;i++)
    {
        res+=d[n][i];
    }
    res%=mod;
    
    printf("%lld\n",res);
    
    return 0;
}

 

 

킥킥 한번에 맞았당ㅎㅎ 볼래?

 

전에 강의들을 떄 한번 푼거 같고 방금은 또 풀었는데 맞아써ㅎㅎㅎㅎㅎㅎ

한 30분? 고민한듯

좋아써 전에는 코드 안보면 풀지도 못했는데 풀었으면 발전하고 이쒀!!!