«   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
47
Total
86,237
관리 메뉴

차근차근

[백준 11057] 오르막 수 본문

대학교/Algorithm

[백준 11057] 오르막 수

SWKo 2020. 1. 22. 19:09

0. 제목

  • 백준 11057 오르막 수
  • BOJ 11057 오르막 수
  • C++ 11057 오르막 수

1. 문제

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


2. 풀이

  • DP 방식을 이용하였다.
  • dp[i][j]는 i단계에서 값이 j일때 오르막 수의 개수를 의미한다.
  • 먼저 처음에 1자리 수일 경우에 대한 초기화를 한다. 즉, 1단계일때 오르막 수는 1개씩(0~9) 뿐이다.
  • 예를 들어, 5단계에서 값이 7일때 오르막 수의 개수를 구하고 싶다면 5단계의 6일때 오르막 수의 개수와 4단계의 7일때 오르막 수의 개수를 합하면 된다.
  • 다음과 같이 써보니 규칙 찾기가 수월하였다.

 

 


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
29
#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int N;
    int dp[1001][10];
    cin >> N;
    
    for(int i = 0; i < 10; i++){
        dp[1][i] = 1;   // 한자리 수일 경우에 대한 초기화
    }
    
    for(int i = 2; i <= N; i++){
        dp[i][0= 1;   //i번째 자리가 0일때는 000.. 이런 형식밖에 없기 때문에 1가지경우
        for(int j = 1; j < 10; j++){
            dp[i][j] = (dp[i][j-1+ dp[i-1][j]) % 10007;
        }
    }
    
    int sum = 0;
    for(int i = 0; i < 10; i++){
        sum += dp[N][i];
    }
    sum %= 10007;
    cout << sum << '\n';
    
    return 0;
}
 
 

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

[백준 9465] 스티커  (0) 2020.01.22
[백준 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
0 Comments
댓글쓰기 폼