«   2022/06   »
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30    
Archives
Today
45
Total
86,235
관리 메뉴

차근차근

[백준 10844] 쉬운 계단 수 본문

대학교/Algorithm

[백준 10844] 쉬운 계단 수

SWKo 2020. 1. 22. 18:58

0. 제목

  • 백준 10844 쉬운 계단 수
  • BOJ 10844 쉬운 계단 수
  • C++ 10844 쉬운 계단 수

1. 문제

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


2. 풀이

  • DP 방식을 이용하였다.
  • dp[i][j]는 i단계에서 값이 j일때 계단 수의 개수를 의미한다.
  • 계단 수란 인접한 모든 자리수의 차이가 1이 나는 수이다. 만약 5단계에서 6일때의 계단수를 알고 싶다면 4단계에서 5일때의 계단 수와 4단계에서 7일때의 계단 수를 합하면 된다.
  • 주의해야할 점이 있는데, 마지막 수가 0, 9일때는 그 전단계의 수가 각각, 1, 8일때만 가능하다.
  • 마지막에 답을 구하기 위해서는 N단계에서의 0일때부터 9일때까지의 계단 수들을 더하면 된다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int N;
    int dp[101][10= {0}; //0으로 초기화 해줘야 함. 다른 수가 섞일 수 있기 때문
    int sum = 0;
    
    cin >> N;
    
    for(int i = 1; i <= 9; i++)
        dp[1][i] = 1;   //1단계에 i일때 쉬운계단의 갯수
    
    for(int i = 2; i <= N; i++){
        dp[i][0= dp[i-1][1];
        dp[i][9= dp[i-1][8];
        
        for(int j = 1; j <= 8; j++)
            dp[i][j] = (dp[i-1][j-1+ dp[i-1][j+1]) % 1000000000;
    }
    
    for(int i = 0; i < 10; i++){
        sum += dp[N][i];
        sum %= 1000000000;
    }
    cout << sum << '\n';
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 2193] 이친수  (0) 2020.01.22
[백준 11057] 오르막 수  (0) 2020.01.22
[백준 10844] 쉬운 계단 수  (0) 2020.01.22
[백준 9095] 1,2,3 더하기  (0) 2020.01.20
[백준 11727] 2×n 타일링 2  (0) 2020.01.20
[백준 11726] 2×n 타일링  (0) 2020.01.20
0 Comments
댓글쓰기 폼