[백준 - C#] 10844번 쉬운 계단 수

문제링크

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

10844번: 쉬운 계단 수

 

 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다.
이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자.
0으로 시작하는 수는 계단수가 아니다.

조건

시간제한 : 1초
메모리 제한 : 256 MB

입력

첫째 줄에 N이 주어진다.
N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

문제정리

1. N이 주어졌을 때 N개인 계단 수를 구해야합니다.
2. 0으로 시작하는 수는 계단수가 아닙니다.

이번 문제의 경우 N의 숫자가 주어졌을 때 N개인 계단 수를 구해야 합니다. 계단 수란 인접한 숫자의 차이가 1인 경우의 수입니다.

저의 경우 dp[자리수, 현재보다 앞의 수] = 경우의 수 로 Array를 만들었습니다.

처음에 dp[1, i] 에 모든 경우의 수를 1로 초기화하고 i는 2자리수부터 N+1까지 반복문을 돌아 모든 경우의 수를 찾습니다.

( 1자리 수는 이미 초기화 하였기 때문에 2자리 수부터 N+1까지 해주면 됩니다. )

 

여기서 주의할 점으로는 2가지가 있는데, 현재 수가 0일 때랑 9일 때인데 0이랑 9일 때는 올 수 있는 전에 숫자가 하나씩 밖에 없기 때문에 예외처리를 하여야 하고 나머지는 그대로 진행하면됩니다.

현재 값이 0 일 경우  => dp [자리수, 0] = dp [자리수 - 1, 1]
현재 값이 9인 경우 => dp [자리수,9] = dp[자리수-1, 9]
나머지 1~8인경우 => dp[자리수,1~8] = dp[자리수-1, (1~8)-1] + dp[자리수-1, (1~8)+1]

그리고 마지막으로 1,000,000,000로 나누어 나머지를 구해야하는데, 안하게 되는 경우 long의 범위를 벗어나 문제가 발생합니다.

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    int N = int.Parse(reader.ReadLine());
 
    long[,] dp = new long[N + 1, 10];
 
    for (int i = 0; i < 10; i++)
        dp[1, i] = 1;
 
    for (int i = 2; i < N + 1; i++) // 자리수
    {
        for (int j = 0; j < 10; j++) // 숫자
        {
            if (j == 0) // 0일 경우 1밖에 나오지 못함
                dp[i, j] = dp[i - 1, 1];
            else if (j == 9)  // 9일 경우 8밖에 오지 못함
                dp[i, j] = dp[i - 1, 8];
            else // 나머지
                dp[i, j] = dp[i - 1, j - 1] + dp[i - 1, j + 1];
 
            dp[i, j] %= 1000000000;
        }
    }
 
    long sum = 0;
 
    for (int i = 1; i < 10; i++)
    {
        sum += dp[N, i];
    }
 
    writer.WriteLine(sum % 1000000000); //  % 1000000000
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.