Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- 모의SW역량테스트
- 완전탐색
- Set
- 레벨2
- C++
- 삼성SW테스트
- 2018
- Map
- 문자열
- 백준
- 삼성
- 레벨3
- 이런게4문제
- Sort
- priority_queue
- 시뮬레이션
- STL
- find
- dfs
- 프로그래머스
- substr
- KAKAO
- 삼성SW역량테스트
- 코딩스킬
- dp
- swea
- 백트래킹
- 코딩테스트
- 브루트포스
- BFS
Archives
- Today
- Total
-
[DP] BOJ 11057번 - 오르막 수 본문
https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.
www.acmicpc.net
DP 연습문제다.
DP[자리수][끝수]라고 정했을 때
맨 윗줄 DP[1][0] ~ DP[1][9]는 모두 1로 선언해준다.
그 다음, DP[N][K] = DP[N-1][0] + DP[N-1][1] + ... + DP[N-1][K]와 같이 점화식을 구성해주면 된다.
아래는 소스코드.
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
31
32
33
34
35
36
37
|
#include <stdio.h>
#pragma warning(disable:4996)
#define div 10007
int main(){
long long DP[1001][10];
for (int r = 0; r <= 1000; r++){
for (int c = 0; c <= 9; c++){
DP[r][c] = 0;
}
}
for (int c = 0; c < 10; c++) DP[1][c] = 1;
for (int r = 1; r <= 1000; r++) DP[r][0] = 1;
int n;
scanf("%d", &n);
if (n == 1){
printf("10\n");
return 0;
}
for (int r = 2; r <= 1000; r++){
for (int c = 1; c <= 9; c++){
for (int b_c = 0; b_c <= c; b_c++){
DP[r][c] += DP[r - 1][b_c];
}
DP[r][c] %= div;
}
if (r == n){
long long ret = 0;
for (int c = 0; c <= 9; c++) {
ret += DP[r][c]; // 모두 더한다음에 모듈러해준다.
}
printf("%lld\n", ret%div);
break;
}
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
'5. DP' 카테고리의 다른 글
[DP] 백준 2011번 - 암호코드 (0) | 2020.01.29 |
---|---|
[DP] BOJ - 10844번 (쉬운계단수) (0) | 2020.01.29 |
[DP] 백준 4811번 - 알약 (0) | 2020.01.28 |
[DP] 백준 5557번 - 1학년 (0) | 2020.01.27 |
[DP] 백준 2193번 - 이친수 (0) | 2020.01.08 |
Comments