[BOJ] 11057번. 오르막 수

www.acmicpc.net/problem/11057

11057번: 오르막 수

모듈러 연산이 또 나왔네요!!

항상 기억하면 좋습니다.

(A+B)%M은 다음과 같습니다.
(A%M + B%M)%M

즉 어떤 답을 모듈러 연산을 통해 도출해야 할 경우, 정답을 구하는 과정에서 나오는 연산의 결과를 계속 모듈러 연산 해주면 됩니다. 

 

[코드 보기]

#include <iostream>
#include <algorithm>
#define mod 10007
using namespace std;

int field[1001][11] = { 0, };

int main()
{
	ios_base::sync_with_stdio(0);
	int n, ans = 10, temp = 0;
	for (int q = 0; q < 10; q++)
	{
		field[1][q] = 1;
	}
	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		field[i][0] = ans;
		for (int j = 1; j < 10; j++)
		{
			for (int p = 0; p < j; p++)
			{
				temp += (field[i-1][p]%mod);
			}
			field[i][j] = (ans - temp)%mod;
			temp = 0;
		}
		ans = 0;
		for (int p = 0; p < 10; p++)
		{
			ans += field[i][p]%mod;
		}
	}
	cout << ans%mod;
	return 0;
}

[설명 보기]

사용자가 입력한 n자릿수의 오르막수를 모두 완성하면 n자릿수의 오르막수를 모두 더하고 출력합니다.

1007은 계속 모듈러 연산을 해줘야 하는 수입니다.

쓰다가 헷갈릴까봐 1007을 미리 mod로 정의해놨습니다.

또한 기억 장소로 2차원 배열을 선언하고 초기화 했습니다.

데이터가 많은 배열은 main 밖에 선언하면 마치 동적 선언한 것만 같은 넓은 저장공간을 사용할 수 있습니다.

이유는...... 데이터 저장영역이 달라서 그랬던 것 같은데... 이건 알아보고 수정할게요... 혹은 아시는 분 수정해주세요.. 

#define mod 10007
int field[1001][11] = { 0, };

오르막수의 성질을 살펴보겠습니다. 

길이가 2인 오르막수는 다음과 같겠습니다.

문제에서 수는 0부터 시작할 수 있다고 했습니다.

그럼 길이가 3인 오르막수는.. 이렇게 생각해보면 될 것 같습니다.

세계관이 확장되었습니다. 맨 앞이 0인 길이 3의 오르막수만 생각해 봅시다.

벌써 0부터 55개입니다.

그럼 맨 앞이 1이면 어떻게 될까요??

아마도, 9+8+7+6....+1 = 45입니다.

 

그러면 우리는 이제 길이가 3인 오르막수의 갯수를 알 수 있습니다.

맨 앞 숫자가 0일때 55개

맨 앞 숫자가 1일때 45개

맨 앞 숫자가 2일때 (8+7+6+...+2+1)개

...

맨 앞 숫자가 9일 때 1개

 

결국 길이가 3인 오르막수의 갯수는 220개네요.
길이가 4인 오르막수의 갯수도 위의 경우와 다르지 않을 것 입니다. 맨 앞 숫자를 고정해놓고 뒤에 올 숫자를 앞에서 재사용합시다.

 

어떤걸 기억해야 하고, 어떤걸 재사용해야할지, 감이 오시나요??

그럼 코드를 다시 보겠습니다.

int main()
{
	ios_base::sync_with_stdio(0);
	int n, ans = 10, temp = 0;
	for (int q = 0; q < 10; q++) field[1][q] = 1;

	cin >> n;

	for (int i = 2; i <= n; i++)
	{
		field[i][0] = ans;
		for (int j = 1; j < 10; j++)
		{
			for (int p = 0; p < j; p++)
			{
				temp += (field[i - 1][p] % mod);
			}
			field[i][j] = (ans - temp) % mod;
			temp = 0;
		}
		ans = 0;
		for (int p = 0; p < 10; p++)
		{
			ans += field[i][p] % mod;
		}
	}
	cout << ans % mod;
	return 0;

}

5번째 줄에서 [1]필드를 1로 초기화 해줍니다. ans는 처음부터 10입니다.

for (int p = 0; p < j; p++)
{
	temp += (field[i - 1][p] % mod);
}

요 부분이 저도 다시 보면서 헷갈렸는데요, 별거 아닙니다.

만약 길이 3인 오르막수의 갯수를 세려면, 길이 2인 오르막수의 갯수를 뒤에 붙여야겠죠!!

아까 봤던 이 사진처럼요!! 

그 부분을 temp에 잠시 저장하고, 새로운 자신의 위치에 저장해 다음 사용을 도모합니다.

 

사용자가 입력한 n자릿수의 오르막수를 모두 완성하면 n자릿수의 오르막수를 모두 더하고 출력합니다.