[백준 11057] 오르막수 문제

오르막수 문제 링크 : https://www.acmicpc.net/problem/11057

11057번: 오르막 수

11057번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 오르막 수 풀이 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 7713 3796 3029 49.300% 문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이 때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하

www.acmicpc.net

오르막수 문제 Java 답 : https://gist.github.com/Baekjoon/7fbfd8d0963139d638de
오르막수 C/C++ 답 : https://gist.github.com/Baekjoon/49b2bfd22be42707bb88

package upstair; import java.util.Scanner; public class Upstair { public static void main(String[] args) { int n,cnt,l=0; Scanner sc=new Scanner(System.in); n=sc.nextInt(); l=sc.nextInt(); int[][] d; d=new int[n][]; System.out.println(counting(n,l)); } public static int counting(int n, int l){ if(n==1){ int result=0; int rep=0; while(rep<=9){ result+=rep; rep+=1; } return result; }else{ return counting(n-1,l); } } }

[1차 풀이]
- N=1 일 때, 10+9+8+'''+1 까지 더해서 55개이다.
 - N=2 일 때, 10^2+9^2 이렇게 해서 제곱의 합을 한다
-N=3 일 때, 10^3+9^3을 해서 합한다.
--> 이러한 풀이는 동적으로 갯수를 계산하기 어렵다. 

[2차풀이]
- D[N][L]= N자리 오르막수의 마지막 수.
- D[N][L]=∑D[N-1][K] (0<=K<=L) 이런 공식이 나온다. 이렇게 되면 역발상으로 마지막 자리수부터 정하고 마지막 자리수 바로 전 숫자를 정하는 방식으로 해야한다. for문이 역으로 돈다.
- 재귀함수를 만들어야 한다.
-D[N][L]= ∑D[N-1][K]
-D[N-1][L]=∑D[N-2][K]
-D[N-2][L]=∑D[N-3][K] 이런식으로 계속 큰거에서 작은 것으로 가야 답을 구할 수 있다.