[백준] 2688 줄어들지 않아

문제

---

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다. 

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

 

 

 

 

풀이

---

해당 문제는 직접 2자릿수 3자릿수를 적어보다 보면 감이 올것이다.

 

2자리수의 경우

0 0 ~ 9 - 9개

1 1 ~ 9 - 8개

2 2 ~ 9 - 7개

...

9 9 - 1개

 

총 9 + 8 + 7 + 6 + ... + 2 + 1 = 55

이 나오게 된다.

 

3자리 수의 경우

0 0 0 ~ 9 - 9개

0 1 1 ~ 9 - 8개

0 2 2 ~ 9 - 7개

...

0 9 9 - 1개

 

1 1 1 ~ 9 - 8개

1 2 2 ~ 9 - 7개

1 3 3 ~ 9 - 6개 

...

1 9 9 - 1개

 

...

 

9 9 9 - 1개

 

위 표현을 보면 점화식 감이 오는가?

 

dp[size][i] = dp[size-1][i] + dp[size-1][i + 1] + dp[size-1][i + 2] ... + dp[size][9] 까지 더하면 된다.

 

위의 식을 이용하여 풀어주면 된다.

 

이경우는 여러번의 계산을 피하고 한번에 64자리수 까지의 값을 모두 구하는 편이 빠르다 생각해서 그렇게 하였다.

 

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static long[][] dp;
	
	public static int parseInt(String stringNumber) {
		return Integer.parseInt(stringNumber);
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int T = parseInt(bufferedReader.readLine());
		
		dp = new long[64][10];
		for(int i = 0 ; i < 10 ; i++) {
			dp[0][i] = 1;
		}
		
		for(int i = 1 ; i < 64 ; i++) {
			for(int j = 0 ; j < 10 ; j++) {
				solution(j, i);
			}
		}
		
		for(int i = 0 ; i < T ; i++) {
			int n = parseInt(bufferedReader.readLine());
			
			long sum = 0;
			for(int j = 0 ; j < 10 ; j++) {
				sum += dp[n - 1][j];
			}
			sb.append(sum + "\n");
		}
		
		System.out.println(sb);
	}
	
	static void solution(int num, int size) {
		
		for(int i = num ; i < 10 ; i++) {
			dp[size][num] += dp[size - 1][i];
		}
	}
}