[백준 11057번 오르막 수/ C++]

www.acmicpc.net/problem/11057

11057번: 오르막 수

 

 

ㅎㅅㅎ 쉬운 계단 수를 풀고 바로 풀어본 문제! 한번 이해하고 나니 ㅎㅅㅎ 뭔가 훨씬 접근 방법이 편했따

 

✅ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%80-10844%EB%B2%88-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EC%88%98-CDP

[백준 10844번 쉬운 계단 수/ C++](DP)

 

 

이또한 2차원 배열에 i길이의 j로 끝나는 오르막 수의 개수를 저장해주면 된다! 

 

	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	10	15	21	28	36	45	55

 

우선 길이가 1인 경우는 모두 하나의 경우밖에 없기 때문에 1로 채워준다. 그리고 길이가 N이면서 0으로 끝나는경우는 모두 하나밖에 없다. 

길이가 2이면서 0으로 끝나려면 00, 3이면서 0으로 끝나려먼 000으로 끝나기 때문이다! 그렇기 때문에 이부분 또한 1로 채워준다. 

 

나머지는 규칙이 보이는가...? 위의 표를 보면 dp[2][1]은 dp[1][1]+dp[2][1]인 것을 알 수 있다...!

그럼 dp[i][j]=dp[i-1][j]+dp[i][j-1]인 것을 알 수 있다.

 

이게 어떻게 나오게 된 것이냐면...!

예를 들어 길이가 2 이면서 3으로 끝나는 경우는(dp[2][3])

03 13 23 33 이 있기 때문에 총 4가지 이다!

 

그럼 길이가 1이면서 0으로 끝나는 경우 + 길이가 1이면서 1로 끝나는 경우 + 길이가 1이면서 2로 끝나는 경우 + 길이가 1이면서 3으로 끝나는 경우를 모두 더해서 dp[2][3]에 넣어주면 된다! 

 

근데 이걸 일일이 계산해주기 싫엉! 이건 dp에 저장돼 있을꺼양! 그래서 3으로 끝나는 경우는 dp[i-1][j]에 저장돼 있고 그 앞에 경우들을 다 더해주어야되는데 이건 사실 dp[2][3]의 전에 아이가 이미 계산해서 저장해놨다! 그게 바로 dp[i][j-1]이기 때문에 dp[i][j]=dp[i-1][j]+dp[i][j-1]가 되는거랍니당 후후

 

 

CODE! ✅

#include <iostream>

using namespace std;
#define mod 10007

int dp[1001][10] = {
    0,
};
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < 10; i++)
        dp[1][i] = 1;

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

        for (int j = 0; j < 10; j++) {
            if (j == 0) {
                dp[i][0] = 1;
                continue;
            }

            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]);
            dp[i][j] %= mod;
        }
    }

    int result = 0;
    for (int i = 0; i < 10; i++)
        result = (result + dp[n][i]);

    cout << result % mod;

    return 0;
}