티스토리 뷰
문제
알고리즘
DP
풀이
해당 수가 증가하는 수 인지 판별하고, 증가하는 수라면 그 수보다 작은 증가하는 수를 찾는 문제입니다.
증가하는 수를 판별하는 건 어렵지 않으니 다음 문제인 개수를 찾는 문제를 생각해봅시다. 증가하는 수의 구조는 최적 부분 구조를 만족하게 됩니다. 현재의 수가 증가하는 수라면 맨 앞자리 하나를 제거한 수 또한 증가하는 수를 만족하기 때문입니다.
$cache [i][j]$= j부터 증가하는 수를 i자리 만들었을 때, 가능한 개수
$cache [i][j]$를 갖고 갱신할 수 있는 상태는 j이하의 수를 맨 앞자리에 붙이는 것입니다. 즉 다음 상태는
$cache [i+1][k]$ (단, k는 j이하의 수이다) 입니다.
나머지의 아이디어는 다음과 같습니다. 123을 예시로 들겠습니다.
- 세 자리 수의 증가하는 수를 모두 구합니다. 이는 $cache [4][0]$과 동일합니다.
- 첫 번째 숫자보다 큰 수에 해당하는 2로 시작하는 세 자리 수의 증가하는 수를 뺍니다.
- 두 번째 숫자보다 큰 수에 해당하는 3으로 시작하는 두 자리 수의 증가하는 수를 뺍니다.
- 세 번째 숫자보다 큰 수에 해당하는 4로 시작하는 한자리 수의 증가하는 수를 뺍니다.
- 이 값은 123을 포함하므로 마지막에 123을 빼기 위해 -1을 수행합니다.
코드
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;
int tc, sl;
long long cache[100][11];//현재까지 만든 자리 수, 시작하는 수
string s;
int main() {
FAST;
for (int i = 0;i < 10;++i) cache[1][i] = 1;
for (int i = 1;i <= 80;++i) {
for (int j = 0;j < 10;++j) {
for (int k = j;k >= 0;--k) {
cache[i + 1][k] += cache[i][j];
}
}
}
cin >> tc;
while (tc--) {
cin >> s;
sl = s.size();
char prv = '0';
bool isInc = true;
for (auto x : s) {
if (prv > x) {
isInc = false;
break;
}
prv = x;
}
if (!isInc) cout << -1 << '\n';
else {
long long ret = 0;
ret += cache[sl + 1][0];
for (int i = 0;i < sl;++i) {
int num = s[i] - '0';
for (int j = num+1;j < 10;++j) {
ret -= cache[sl - i][j];
}
}
cout << ret-1<< '\n';
}
}
return 0;
}
'Algorithm' 카테고리의 다른 글
[백준 3584] 가장 가까운 공통 조상 (0) | 2020.10.08 |
---|---|
[백준 12014] 주식 (0) | 2020.10.05 |
[백준 17365] 별다줄 (0) | 2020.09.29 |
[백준 17291] 새끼치기 (0) | 2020.09.28 |
[백준 3257] 발코딩 (0) | 2020.09.24 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 좌표압축
- Segment tree
- 트라이
- Oracle
- dijkstra
- hld
- 이분매칭
- greedy
- Fenwick
- kmp
- 세그먼트트리
- knapsack
- 2-SAT
- Suffix Array
- SCC
- sorting
- spring boot
- 이분탐색
- DP
- dfs
- spring
- implementation
- 펜윅트리
- sweeping
- string
- 동적계획법
- union find
- 스위핑
- 정렬
- bfs
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함