문제 링크
문제
티어: 골드 3
알고리즘: dp
증가하는 수는 수의 각 자리가 증가하거나 같은 경우이다.
예를 들어서, 다음 세 가지 수를 보자.
- 123
- 101
- 1111000001111
123은 1<2<3이므로 증가하는 수이다. 하지만 101은 1>0<1이고, 1111000001111은 1=1=1=1>0=0=0=0=0<1=1=1=1이므로 증가하는 수가 아니다.
입력
입력은 테스트 케이스의 수로 시작한다.
각 테스트 케이스에는 한 자연수만 있다. 자연수는 80자리 수를 넘지 않는다.
출력
각 테스트 케이스별로 판단한다.
수가 증가하는 수가 아니면, -1을 출력한다.
그 수가 증가하는 수이면, 그 수보다 작은 증가하는 정수의 개수를 출력한다.
각 테스트 케이스별 출력은 64-bit 길이여야 한다.
풀이
수가 증가하는 수라면 그 수보다 작은 증가하는 정수의 개수를 출력해야 한다.
입력의 수는 최대 80자리이기 때문에 완탐은 불가능하다.
증가하는 수를 구해야 하기 때문에 중복된 경우가 있는지를 찾고, 메모제이션을 활용하는 dp 알고리즘을 생각할 수 있다.
먼저,
길이가 1인 증가하는 수를 구해보자
1, 2, 3, 4, ..9로 9가지 존재한다.
길이가 2인 증가하는 수를 구해보자
11, 12, 13, 14, 15, ..19
22, 23, 24, 25, 26, ..29
..
이렇게 존재하는데
잘보면 길이가 1인 증가하는 수가 포함된 것을 알 수 있다.
그래서
1x 일때 9개
2x 일때 8개
3x 일때 7개
..
이렇게 구해줄 수 있고,
길이가 3인 증가하는 수를 구할 때도 다음과 같은 방식으로 구할 수 있다.
1xx 일때는 1x + 2x + 3x + 4x + ..9x
2xx 일때는 2x + 3x + 4x + 5x + ..9x
그래서 길이가 1일때 부터 증가하는 수를 구하고, 현재 길이 - 1의 저장된 값을 활용하면 중복 탐색없이 자릿수마다 9번의 탐색만으로 구할 수 있게 된다.
이를 토대로 dp를 정의하면
dp[A][B] -> A는 자리 (오른쪽 부터 1), B는 A자리의 수를 의미하고, dp[2][3]이면 2번째 자릿수가 3일 때의 증가하는 수의 개수를 의미한다. (3x)
그래서 dp[1][1] ~ dp[80][9] 까지 먼저 구한 뒤
1234보다 작은 모든 증가하는 수를 구하는 방법은 다음과 같다.
-
먼저 정수의 개수를 구하기 때문에 0을 먼저 더해준다.
-
길이가 4, 3, 2, 1일때 모든 증가하는 수를 더해준다. 그러면 그 수보다 같거나 큰 1234, 1235, 2222,...9999까지 더해졌기 때문에 이 수를 뻬야된다.
-
dp[4][2], dp[4][3] .. dp[4][9]까지 빼주고
-
dp[3][3], dp[3][4] .. dp[3][9]까지 빼주고
..
이렇게 첫 번째 자리까지 반복해준다. -
그러면 1234를 포함하고, 이보다 작은 증가하는 정수의 개수를 모두 구했고, 1234를 포함하면 안되기 때문에 -1를 해주면 답이 된다.
이 풀이의 시간 복잡도는 자리마다 9번씩 반복하기 때문에 O(80 * 9)가 된다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
long[][] dp = new long[81][10]; //[A][B] -> A는 자리(오른쪽 부터 1) B는 그 자릿수 (0은 총 합을 의미) 그래서 [2][1]은 2번째 자릿수가 1일 때 증가하는 수의 총합
long[] totalDigits = new long[81]; //[3]이면 3자리 + 2자리 + 1자리의 모든 증가하는 수의 합임 0포함
for(int i=1; i<=9; i++) {
dp[1][i] = 1;
dp[1][0] += dp[1][i];
}
totalDigits[1] = 10;
for(int i=2; i<=80; i++) {
long v = 0; //뺄 값;
for(int j=1; j<=9; j++) {
dp[i][j] = dp[i - 1][0] - v;
dp[i][0] += dp[i][j];
v += dp[i - 1][j];
}
totalDigits[i] += dp[i][0] + totalDigits[i - 1];
}
StringBuilder sb = new StringBuilder();
for(int t = 0; t < T; t++) {
String input = br.readLine();
if(!isPosible(input)) {
sb.append(-1).append("\n");
continue;
}
//증가하는 수임 이 수보다 작은 개수를 출력해야 됨
long answer = totalDigits[input.length()]; //0을 포함
for(int i=input.length(); i>=1; i--) {
int ind = input.length() - i;
int num = input.charAt(ind) - '0';
//큰 자리부터 첫 번째 자리까지
for(int j=num + 1; j<=9; j++) {
answer -= dp[i][j];
}
}
answer -= 1; //자기 자신 빼기
sb.append(answer).append("\n");
}
System.out.println(sb.toString().trim());
}
static boolean isPosible(String str) {
int before = str.charAt(0) - '0';
for(int i=1; i<str.length(); i++) {
int cur = str.charAt(i) - '0';
if(before > cur) {
return false;
}
before = cur;
}
return true;
}
}