[코딩테스트 C++] 쉬운 계단 수

오늘의 문제

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

쉬운 계단 수

접근 방법

• 0과 9의 경우만 각각 1, 8의 개수와 같고, 나머지는 앞 뒤의 개수의 합이다.
• 문제의 조건에 맞게 DIV(1000000000)으로 나눈 값을 출력하면 된다.

나의 풀이

#include<iostream>
#include <algorithm>
using namespace std;
int n;
const int DIV = 1000000000;
int solution(){
    int num[10] ={0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    int temp[10];
    
    for(int i=1;i<n;i++){
        temp[0] = num[1];
        temp[9] = num[8];
        for(int j=1;j<9;j++)
            temp[j] = (num[j-1]+num[j+1])%DIV;
        for(int i=0;i<10;i++)
            num[i] = temp[i];
    }
    int answer =0;
    for(int i=0;i<10;i++)
        answer = (answer + num[i])%DIV;
    return answer;
}

다른 풀이

#include <stdio.h>

int main()
{
	int n, dp[101][10] = { 0 };
	long long result = 0;

	scanf("%d", &n);
	for (int i = 0; i <= 9; i++)
		dp[1][i] = 1;

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

	for (int i = 1; i <= 9; i++)
	{
		result += dp[n][i];
		result %= 1000000000;
	}

	printf("%lld", result);

	return 0;
}

배울 점

• 이분은 101 *10, 나는 20칸짜리 배열을 사용했는데, 메모리가 더 작게 잡힌다. 럴수가