[백준/C++] 알고리즘 10844번 - 쉬운 계단 수

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 10844번 - 쉬운 계단 수 를 풀어보도록 하겠습니다.

 

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

10844번: 쉬운 계단 수

 

[문제 접근]

이전 상황을 이용하여 현재 상황을 이루는 문제이기 때문에 다이나믹 프로그래밍으로 접근했습니다.

패턴을 찾기 위해 처음에는 곧이곧대로 n = 1,2,3일 때를 모두 종이에 써가며 확인했습니다. 자연스럽게 상황마다 0~9까지의 숫자의 개수를 세기 시작했고, 이전 상황의 숫자들의 개수와 현재 상황의 숫자들의 개수의 연관성이 보였으나 패턴을 못 찾았습니다.

그래서 0~9까지의 개수를 n = 1,2,3 .... 일때를 테이블 형태로 종이에 적어보고나서야 패턴을 발견했습니다.

 

-현재상황의 0의 개수는 이전상황의 1의 개수와 동일.

- 현재상황의 9의 개수는 이전상황의 8의 개수와 동일.

- 현재상황의  j의 개수는 이전상황의 j-1의 개수 이전상황의 j+1의 개수의 합과 동일

 

패턴을 발견하고나서, dp[i][j]의 정의가 자연스레 떠올랐고, 이를 이용하여 풀이를 진행했습니다.

추가로 출력이 1,000,000,000으로 나눈 나머지 출력인데 dp의 값을 저장할 때 1,000,000,000으로 나눈 나머지값을 저장하지 않으면

틀립니다. (숫자가 워낙 커서)

 

[풀이 전략]

1. dp[1][j]를 초기화합니다.

2. 아래의 점화식을 이용하여 dp값들을 채웁니다. 이때 1,000,000,000으로 나눈 나머지값을 저장해야 합니다.

- dp[i][0] = dp[i-1][1],

- dp[i][9] = dp[i-1][8]

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

3. dp[n][0]부터 dp[n][9]까지의 합을 모두 더한 다음 1,000,000,000으로 나눈 나머지값을 출력합니다.

 

[코드]

#include <iostream>
#include <algorithm>
using namespace std;


int n ;

long long dp[101][10];
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ;
    
    dp[1][0] = 0 ;
    for(int j = 1 ; j < 10 ; j++) dp[1][j] = 1;


    for(int i = 2 ; i <= 100 ; i++)
        for(int j = 0 ; j < 10 ; j++){
            if(j == 0) dp[i][0] = dp[i-1][1] % 1'000'000'000 ;
            else if(j == 9) dp[i][9] = dp[i-1][8] % 1'000'000'000;
            else dp[i][j] = dp[i-1][j-1] % 1'000'000'000 + dp[i-1][j+1] % 1'000'000'000;
        }
        
    long long sum = 0 ;
    for(int j= 0 ; j < 10 ; j++) sum += dp[n][j] % 1'000'000'000; 
    cout << sum % 1'000'000'000 ; 
}

[배울 점]

- 모듈러 연산 공식 : (a+b) mod c = (a mod c + b mod c) mod c