알고리즘
[BOJ] 줄어들지 않아
winwin-k9
2024. 5. 1. 18:07
문제
어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.
예를 들어, 1234는 줄어들지 않는다.
줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.
이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.
n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.
풀이
먼저 규칙을 파악해야 했다.
2차원 배열을 기준으로 파악해보자.
행을 자릿 수, 열을 자릿수중 가장 큰 수 라고 했을 때 다음과 같은 규칙이 발생한다.
| 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|
| 2 | 3 | 4 | 5 | 6 |
| 3 | 6 | 10 | 15 | 21 |
1번째 자릿수는 항상 1개이고, 2번재 자릿수 부터 아래와 같은 규칙이 나온다.
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]위를 만족시키는 DP를 구현한 후, 각 자릿수의 행을 모두 더하면 된다.
주의할점은 위의 식은 0으로만 이루어진 수를 포함하지 않는다.
따라서 행을 모두 더한 후 0으로만 이루어진 자릿수를 포함하기 위해서 1을 추가로 더해준다.
import java.lang.*;
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
List<Integer> list = new ArrayList<>();
for (int i = 0; i < T; i++) {
list.add(Integer.parseInt(br.readLine()));
}
int max = Collections.max(list);
long[][] dp = new long[max + 1][10];
for (int i = 1; i <= 9; i++) {
dp[1][i] = 1;
}
for (int i = 1; i <= max; i++) {
dp[i][1] = i;
}
for (int i = 2; i <= max; i++) {
for (int j = 2; j <= 9; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
for (Integer integer : list) {
System.out.println(Arrays.stream(dp[integer]).sum() + 1);
}
}
}728x90