[BOJ/백준] 10844 쉬운 계단 수

● [문제번호 10844] 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

● 풀이 과정

: 풀릴 듯 말 듯한 고민 끝에 구글링을 하였다.

코드를 보고 채점하고 풀이과정까지 작성해서야 완전히 이해했다.

 

: 자릿수가 낮을 수록 높은 자리의 숫자를 의미한다.

예를 들어 자릿수가 5라면

자릿수 1에 있는 3은 34567과 같은 10,000단위의 숫자가 3이라는 뜻이다.

 

1. 테이블 정의

→ 각 자릿수에서 1단위 수가 num인 경우의 계단 수의 총 갯수이다.

 

2. 점화식 찾기

→ dp[digit][num] = dp[digit - 1][1]

num == 0 인 경우 : 이전 자릿수의 num이 1인 경우에서만 온다.

 

→ dp[digit][num] = dp[digit - 1][num - 1] + dp[digit - 1][num + 1]

1 ≤ num ≤ 8 인 경우 : 이전 자릿수의 num이 ±1인 경우에서 온다.

 

→ dp[digit][num] = dp[digit - 1][8]

num == 9 인 경우 : 이전 자릿수의 num이 8인 경우에서만 온다.

 

3. 초기값 정하기

→ 자릿수가 1자리 일 때 값만 입력하면 된다.

→ 문제에서 '0으로 시작하는 수는 없다.'고 주어져있으므로 자릿수1의 0은 0이다.

 

복잡해 보이지만 간단합니다! / 2차원 배열을 표로 표현

붉은 칸 : 자릿수 (아래 코드에서 digit)

초록 칸 : 2차원 배열의 열 부분 (아래 코드에서 num)

파란 칸 : 각 자릿수의 계단 수 총 갯수

회색 칸 : 초기값

흰색 칸 : 이전 자릿수의 빨간색 화살표로부터 받은 값

노란 칸 : 이전 자릿수에서 보라색 화살표와 초록색 화살표로부터 받은 값

 

 

● 주의 할 것

: 문제에서 '0으로 시작하는 수는 없다.'고 주어져있으므로 자릿수1의 0은 0임을 주의한다.

 

● 참고 할 것

: Top-Down 방식, Bottom-Up 방식 모두 있는 링크

https://st-lab.tistory.com/134

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// int dp[101][10]; 와 동일한 배열
vector<vector<long long>> dp(101, vector<long long>(10, 0));
int N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 초깃값
    dp[1][0] = 0;
    for(int num = 1; num < 10; num++)
        dp[1][num] = 1;
    
    // 다이나믹 프로그래밍
    // 자릿수가 2인 경우부터 시작
    for(int digit = 2; digit <= N; digit++)
    {
        // 해당 자릿수의 숫자가 0 ~ 9
        for(int num = 0; num < 10; num++)
        {
            // 0인 경우는 이전 자릿수의 숫자가 1인 경우
            if(num == 0)
                dp[digit][0] = dp[digit - 1][1];
            // 9인 경우는 이전 자릿수의 숫자가 8인 경우
            else if(num == 9)
                dp[digit][9] = dp[digit - 1][8];
            // 1 ~ 8인 경우는 이전 자릿수의 숫자가 현재 자릿수의 숫자의 ±1인 경우
            else
                dp[digit][num] = dp[digit - 1][num - 1] + dp[digit - 1][num + 1];
            
            // 1000000000을 넘을 수 있는 숫자에 대해 나머지를 저장
            dp[digit][num] %= 1000000000;
        }
    }
    
    // 구하고자하는 자릿수의 계단 수 갯수 총합
    long long result = 0;
    for(int num = 0; num < 10; num++)
    {
        result += dp[N][num];
    }
    
    // 총합이 1000000000을 넘을 수 있으므로 나머지를 출력
    cout << result % 1000000000;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [400 - 다이나믹 프로그래밍 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1463	1로 만들기	https://pirateturtle.tistory.com/199
2	11726	2×n 타일링	https://pirateturtle.tistory.com/200
3	11727	2×n 타일링 2	https://pirateturtle.tistory.com/201
4	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/202
5	11052	카드 구매하기	https://pirateturtle.tistory.com/203
6	16194	카드 구매하기 2	https://pirateturtle.tistory.com/204
7	15990	1, 2, 3 더하기 5	https://pirateturtle.tistory.com/205
8	10844	쉬운 계단 수	https://pirateturtle.tistory.com/206
9	2193	이친수	https://pirateturtle.tistory.com/207
10	11053	가장 긴 증가하는 부분 수열	https://pirateturtle.tistory.com/208
11	14002	가장 긴 증가하는 부분 수열 4	https://pirateturtle.tistory.com/209
12	1912	연속합	https://pirateturtle.tistory.com/210
13	1699	제곱수의 합	https://pirateturtle.tistory.com/211
14	2225	합분해	https://pirateturtle.tistory.com/212