Baekjoon11057-오르막 수

백준 사이트 11057 - 오르막 수 문제입니다.

1. 문제

https://www.acmicpc.net/problem/11057

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다.
비슷한 문제를 안풀어봤으면 어렵다는 생각이 들 수 밖에 없습니다. DP를 2차원으로 써야하기 때문입니다.
공책으로 먼저 그려나가면서 규칙을 찾으면 쉽게 풀 수 있습니다.

백준에서는 Sliver1의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

dp[2][2]인 경우 (02,12,22) 세 가지 경우인데 (02,12)는 이미 DP[2][1]에서 세준거나 다름 없습니다.
중요한건 뒷자리수가 아니라 그 앞에 뭐가 오느냐가 중요한 것이기 때문입니다.
dp[3][2]인 경우 (002,012,112,022,122,222)로 총 6가지입니다.
여기서 022,122,222는 맨 뒷숫자 2를 제외하면 02,12,22인데 이것은 앞에서 설명한 dp[2][2]와 같습니다.
나머지 002,012,112도 맨 뒷숫자 2를 제외하면 00,01,11인데 이것은 dp[3][1]와 같습니다.
dp[N][0]인 끝자리가 0으로 끝나는 경우 0,00,000 .. 밖에 못오므로 무조건 1입니다.
마지막에 10007로 나눠주는 것도 까먹지 않고 수행해야합니다.

---

5. code

#include<iostream>

using namespace std;

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

}

void Solve()
{
	for (int i = 2; i <= n; ++i)
	{
		for (int j = 1; j < 10; ++j)
		{
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 10007;
			if (i == n)
			{
				result += dp[i][j];
				result %= 10007;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	Solve();
	if (n == 1)
		cout << 10;
	else
		cout << result;
}

---

6. 후기

안풀어봤으면 어떻게 이런문제를 다시 생각하기 힘들지 않을까