C++/DP
DP - 11057(오르막 수)
꿈을보는섬
2021. 1. 6. 23:06
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
해당 문제를 풀기전
DP - 10844(쉬운 계단 수) :: 꿈을 보는 개발자 (tistory.com)
DP - 10844(쉬운 계단 수)
10844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉬운 계단 수 문제였지만 마냥 쉽지만은 않았습니다. 우선 2차원 배열
islandofdream.tistory.com
위 문제에 대해서 이전 게시물에 포스팅하였습니다.
오르막 수 문제도 이와 비슷한 갈피를 통해서 문제를 풀었습니다. 여기서 쉬운 계단 수와 다른 점은 쉬운 계단 수는 1과 9일 경우에만 조건을 통해서 설정 해주었지만, 이 경우에는 자리에 들어갈 숫자보다 같거나 큰 경우에만 값을 넣을 수 있습니다. 그렇기 때문에 이전 문제를 활용하여서 for을 0~9까지 검사하도록 해주고 현재 자리수의 숫자보다 크거가 값은 경우에는 값을 더해서 갱신 해주도록 하였습니다.
package com.company;
import java.util.Scanner;
public class Main {
static int number[][] = new int[1001][10];
public static int cal(int level , int num){
int sum = 0;
for(int i =0; i<10; i++){
number[1][i] = 1;
}
for(int i=2; i<=level; i++){
for(int j = 0; j<num; j++){
for(int n=9; n>=j; n--){
number[i][j] += (number[i-1][n])%10007;
}
}
}
for(int k =0; k<10; k++){
sum += number[level][k];
}
return sum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(cal(n,10)%10007);
}
}