[PS] BOJ_10844

BOJ_10844

💡 생각하자

Dynamic Programming(동적 계획법)의 개발절차
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기

먼저, N=2인 경우(AB)를 생각해보자.
10, 12, 21, ⋯ ,87, 89, 98이 가능하다.

다음으로, N=3인 경우(ABC)를 생각해보자.

A는 1~9가 가능하다. 이제 뒤의 두자리 BC를 구해야하는데, 이는 이미 N=2인 경우에서 구했다.
하지만 여기서 한가지 신경써야 할 것은 A에 따라서 B에 올 수 있는 수가 정해져있다는 것이다.

예를들어, A=3이면 B는 2 또는 4만 가능하다. 그러면 N=2인 경우에서 2, 4로 시작하는 것들이 가능하다.

A가 2~8일 때는 위와 동일하지만, 1과 9일 때는 따로 생각해주어야 한다.
예를 들어, A=1이면 B는 0과 2만 가능하다. 그리고 A=9이면 B는 8만 가능하다.

재귀 관계식
D[i][j] : 길이가 j이고 i로 시작하는 계단 수의 개수
D[i][j] = D[i-1][j-1] + D[i+1][j-1]

- A=1인 경우에는 B가 0 또는 2이다. 여기서 2인 경우는 쉽게 구할 수 있으니 넘어가고, 0인 경우에 대해서 생각해보자.

그림에서 표시된 것 처럼 N=4에서 AB=10일 때, C는 무조건 1이 되어야한다. 그러므로 N=2이고 1로 시작하는 경우의 수를 구하는 것과 동일하다.

- A=9인 경우를 따로 나누지 않고, A=10인 경우(실재로 성립하지는 않지만)를 만들어주어 계산을 편하게 해주었다.

💻 구현하자

• 초기 호출문

// init
for (int i = 0;i <= 9;i++)
	D[i][1] = 1;

for (int i = 1;i <= n;i++)
	D[10][i] = 0;

int res = calNum(n);

- N=1일 때는 자명하므로 모두 1로 초기화 해준다.
- 10번째 행은 실제로 존재할 수 없지만, 계산의 편의를 위해 만들어서 0으로 초기화 해준다.

• 길이가 N인 계단 수의 개수를 구하는 함수

int	calNum(int n) {
	int res = 0;

	for (int j = 2;j <= n;j++) {
		D[0][j] = D[1][j - 1];

		for (int i = 1;i <= 9;i++) {
			D[i][j] = (D[i - 1][j - 1] + D[i + 1][j - 1]) % 1000000000;
		}
	}

	// sum
	for (int i = 1;i <= 9;i++) {
		res += D[i][n];
		res = res % 1000000000;
	}

	return res;
}

- j는 N, i는 행을 의미한다.
- 각 열을 계산하기 전에, 가장 먼저 D[0][j]값을 만들어준다.

💥 발전하자

• 에러 및 해결

1. 처음에는 마지막 결과 값에만 %10⁹을 해주었다. 하지만 입력 값이 커지면 오버플로우가 발생하여 DP 테이블을 갱신할 때 마다 해주는 것으로 수정했다.

📌 참고하자

나의 코드(Github)