[백준 10844번] 쉬운 계단 수

BOJ 10844번 쉬운 계단 수

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

백준 10844번 C++ 소스

DP배열 index를 0부터 시작해도 되지만 편의상 1자리수 일 때 1로  index를 시작하였기에 

DP배열의 범위가 벗어나지 않게 여유롭게  DP[103][13]을 선언했다.

변수 i는 현재 자리수를 나타내는 변수이고,

변수 j는 0~9까지 루프를 돌게 되는데 첫자리가 아닌  끝자리가 0~9로 적용한 것이다. 

끝자리가 0일때는 바로 앞자리에 1만 올 수 있고, 끝자리가 1일땐 바로 앞자리에 0또는 2가 올 수 있다. 

끝자리가 9일때는 바로 앞자리에 8만 가능할 것이다. 

또한, 실질적 연산은 N이 2이상 입력되었을 때 진행되며, N이 1일때는 solve함수가 실행되지 않는다. 

N이 2이상 입력되었을 때 N이 1일때에 관한 DP배열 정보가 필요하므로 1자리수 일때 일일이 

직접 값을 넣어주었다.

이 원리로 점화식을 세워보면  다음과 같이 3가지 경우로 나뉜다.

 끝자리가 0 일 때

DP[i][j] = DP[i - 1][j + 1]

 끝자리가 9 일 때

DP[i][j] = DP[i - 1][j - 1]

 끝자리가 1~8 일 때

DP[i][j] = (DP[i - 1][j + 1] + DP[i - 1][j - 1])

---

점화식 설명 및 예시

DP[2][0]은 2자리수중 0으로 끝난다.

바로 앞자리에 숫자 1이 가능할 것이며, 이 값을 DP[1][1]에서 가져오는 방식이다. 

DP[2][1]은 2자리수중 1로 끝난다.

바로 앞자리에 0 and 2가 가능할 것이며, 이 값을 DP[1][0]이랑 DP[1][2] 에서 가져오는 방식이다.

DP[1][0]은 1자리수중 0으로 끝나고, 이 값은 0이기 때문에 0으로 초기화 하고 시작했다.  

ex) 3자리수 중 1로 끝나는 수는 몇 개인지 구해보기.

DP[3][1]을 구하면된다. 끝자리가 1로 끝나니깐 바로 앞 전 숫자가 0또는 2가 나와야한다.

DP[2][0] = 2자리수중 0으로 끝나는 숫자는 1개 있었음.

DP[2][2] = 2자리수중 2로 끝나는 숫자는 2개 있었음.

따라서 DP[3][1] = DP[2][0] + DP[2][2] 은 

101

121

321

총 3개가 되는 것이다.

---

나머지연산에 관한 설명 

연산과정에서 오버플로우가 발생할 수 있기 때문에 DP배열에 저장하면서 수시로 나머지연산을 하며,

DP배열을 다 채우고 마지막에 res를 더해나갈때도 오버플로우 예방을 위해 나머지연산을 해준다.

---

입출력 예시

45

516874370

97

549712215

13

21053

#include "pch.h"
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

long long solve(int N)
{
	long long DP[103][13], res = 0;
	int i, j;

	DP[1][0] = 0;
	for (i = 1; i < 10; i++)
	{
		DP[1][i] = 1;
	}

	for (i = 2; i <= N; i++)
	{
		for (j = 0; j < 10; j++)
		{
			// 끝자리가 0 일 때
			if (!j)
			{
				DP[i][j] = DP[i - 1][j + 1] % 1000000000;
			}
			// 끝자리가 9 일 때
			else if (j == 9)
			{
				DP[i][j] = DP[i - 1][j - 1] % 1000000000;
			}
			// 끝자리가 1~8 일 때
			else
			{
				DP[i][j] = (DP[i - 1][j + 1] + DP[i - 1][j - 1]) % 1000000000;
			}
		}
	}
	
	for (i = 0; i < 10; i++)
	{
		res += DP[N][i] % 1000000000;
	}
	return res % 1000000000;
}

int main(void)
{
	int N;

	cin >> N;
	if (N == 1)
	{
		cout << 9 << endl;
	}
	else
	{
		cout << solve(N) << endl;
	}

	return 0;
}

비쥬얼 스튜디오 2017.