백준 10844번 _ 쉬운 계단 수

2020-05-09 · 배운 것 · 3분 읽기

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

10844번: 쉬운 계단 수

주의사항

%를 계산시마다 할것!!!

전체코드

재귀 풀이

#include <iostream>
#define DIV_NUM 1000000000

using namespace std;
long long dp[10][101];
int N;

void dpInit()
{
	for (int i = 0; i <= 9; i++)
		for (int j = 1; j <= N; j++)
			dp[i][j] = -1;
}

long long getCount(int number, int n)
{
	long long& ret = dp[number][n];
	if (ret != -1) return ret;

	//기저사례
	if (n == N)
		return ret = 1;

	ret = 0;
	if (number == 0)
		ret += getCount(number + 1, n + 1);
	else if (number == 9)
		ret += getCount(number - 1, n + 1);
	else
	{
		ret = (ret + getCount(number - 1, n + 1)) % DIV_NUM;
		ret = (ret + getCount(number + 1, n + 1)) % DIV_NUM;
	}
	return ret%DIV_NUM;
}

void solve()
{
	long long cnt = 0;
	for (int number = 1; number <= 9; number++)
		cnt = (cnt + getCount(number, 1)) % DIV_NUM;
	cout << cnt;
}

int main()
{
	cin >> N;
	dpInit();
	solve();
	return 0;
}

반복문 풀이

#include <iostream>
#include <algorithm>

using namespace std;

long long int dp[102][11];

int main(void)
{
	int n;
	cin >> n;
	long long int result = 0;

	for (int j = 1; j <= 9; j++)
	{
		dp[1][j] = 1;
	}

	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			if (j == 0)
			{
				dp[i][j] = dp[i - 1][j + 1];
			}
			else
			{
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
			}
			dp[i][j] %= 1000000000;
		}
	}
	
	for (int j = 0; j <= 9; j++)
	{
		result += dp[n][j];
		result %= 1000000000;
	}

	cout << result;
	return 0;
}

후기

한 몇일간 dp문제만 주구장창 풀어서 쉬운 문제는 풀수있을만큼 감을 다시 잡은것같다. 며칠전까지만 해도 풀었던 문제도 어떻게 풀었는지 기억이 안나 좌절했었는데 다행이다.ㅎㅎ