Easy is Perfect

[백준] 11507번 C/C++ 풀이 _ 오르막 수

  • melonicedlatte
  • Nov 20, 2018


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

오르막 수 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초256 MB119235756455147.895%

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 

1

예제 출력 1 

10

예제 입력 2 

2

예제 출력 2 

55

예제 입력 3 

3

예제 출력 3 

220

출처

알고리즘 분류

풀이

오르막 수는 이전 오르막수의 끝자리를 살펴서 계속해서 갱신합니다.
dp[자리수][끝나는 숫자] 이기 때문에 해당 자리수를 갱신하려면 dp[자리수-1][끝나는 숫자보다 적거나 같은 얘들]
을 전부 더해주어야 합니다.

구현은 아래와 같습니다. 
다른 풀이도 첨부했으니 참고해주세요~

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream> 
#define N_MAX 1000+1
#define DECI 10
#define DIV 10007
int main() { 
    int N; scanf("%d", &N);
    int dp[N_MAX][DECI] = { {0},{1,1,1,1,1,1,1,1,1,1} };
    for (int dp_idx = 2; dp_idx <= N; dp_idx++) 
        for (int deci_now = 0; deci_now < DECI; deci_now++) 
            for (int deci_bef = deci_now; deci_bef < DECI; deci_bef++) 
                dp[dp_idx][deci_now] += (dp[dp_idx - 1][deci_bef]%DIV);
 
    int ans = 0; 
    for (int deci_idx = 0; deci_idx < DECI; deci_idx++)
        ans += dp[N][deci_idx];
    printf("%d", ans%DIV);
    return 0;
}
cs

다른 풀이

1
2
3
4
5
6
7
8
#include <cstdio>
int main() {
    int n, ans = 1; scanf("%d", &n);
    for (int i = 1; i <= 9; ++i)
        ans = ans * (n + i) % 10007;
    printf("%d", ans * 6995 % 10007);
    return 0;
}
cs



Search