-
[알고리즘-JAVA] 백준 알고리즘 11057번 - 오르막수알고리즘 2019. 8. 5. 15:25
접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?수의 길이 N이 주어졌을 때, 수의 자리가 오름차순을 이루는 수인 오르막수의 개수를 구하는 문제
2. 나의 방식대로 문제를 재정의 하자.d[n][k] = 길이가 n이고, 끝자리가 k로 끝나는 오르막수의 개수.
sum(d[n][k]) (0<=k<=9)를 구한다.
3. 어떤 알고리즘과 자료구조를 사용할 것인가?재귀(Top-Down), 반복문(Bottom-UP)
4. 어떻게 계산할 것인가?
1) 입력BufferedReader, InputStreamReader를 이용
2) 시간 복잡도 계산
d[n]의 한줄의 라인을 끝까지 읽으므로 O(N)이다.
5. 주의할 점은 무엇인가?처음 자리가 0이 와도 상관없다고 했기 때문에
d[1][k] = 10이라는점!
6. 풀이 과정
d[n][l] = n자리의 숫자중에서 L로 끝나는 오르막수의 갯수라고 하면,
아래의 점화식과 같이 나타낼 수 있다.
이때 k의 범위는 L과 같아도 되므로 0<=k<=L임에 주의한다!
Bottom-UP
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main{ public static long d[][]; public static void main(String args[])throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); d = new long[n+1][10]; for (int i = 0; i <= 9; i++){ d[1][i] = 1; } for (int i = 2; i <= n; i++){ for (int j = 0; j <= 9; j++){ for (int k = 0; k <= j; k++){ d[i][j] += d[i-1][k]; d[i][j] %= 10007; } } } long sum = 0; for (int i = 0; i <= 9; i++){ sum += d[n][i]; sum %= 10007; } System.out.println(sum); } }
Top-Down
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main{ public static long d[][]; public static void main(String args[])throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); d = new long[n+1][10]; long sum = 0; for (int i = 0; i <= 9; i++){ sum += Calculate(n, i); } System.out.println(sum % 10007); } public static long Calculate(int n, int k){ if (n==1){ return 1; } if (d[n][k] > 0){ return d[n][k]; } for (int i = 0; i <= 9; i++){ for (int j = 0; j <= i; j++){ d[n][i] += Calculate(n-1, j); d[n][i] %= 10007; } } return d[n][k]; } }
'알고리즘' 카테고리의 다른 글
[알고리즘-JAVA] 백준 알고리즘 10430번 - 나머지 (0) 2019.08.06 [알고리즘-JAVA] 백준 알고리즘 9465번 - 스티커(미완) (0) 2019.08.06 [알고리즘-JAVA] 백준 알고리즘 10844번 - 쉬운 계단 수 (0) 2019.08.04 [알고리즘-JAVA] 백준 알고리즘 2193번 - 이친수 (1) 2019.08.03 [알고리즘-JAVA] 백준 알고리즘 11052번 - 카드 구매하기 (0) 2019.08.02