사용한 알고리즘
알고리즘 설명
- 입력받은 값에 시계수를 먼저 찾아낸다. 찾는 방법은 숫자를 한쪽으로 밀면서 최소 값을 찾는다.
- 이 알고리즘에서는 왼쪽으로 밀었다. 예를 들면 1221 -> 2211 -> 2112 -> 1122 으로 4번만 밀어보면 시계수를 찾을 수 있다.
- DFS로 4자리에 시계수를 찾아서 현재 시계수 값보다 작은 개수를 찾아 출력하면 된다.
- 시계수 생성법은 아래와 같다.
- 1번째 수는 아무거나 상관 없다.
- 2번째 수는 1번째 수보다 크거나 같아야 한다.
- 3번째 수는 1번째 수보다 크거나 같아야 한다.
- 4번째 수는 131 과 같이 1번째와 3번째 수가 같은 경우 2번째 수보다 크거나 같아야 한다.
- 위 경우가 아닌 경우 1번째수보다 커야한다. 같은 경우에는 더 작은 시계수가 생길 수 있다. ex(1321 -> 1132)(X) (1322)(O)
풀이
// baekjoon 2659 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
int N, x, tmp;
int dfs(int cost, int pos) { // cost : now cost, pos Number of choose number
int ret = 0;
if (pos == 4) {
return cost <= N;
}
if (pos == 0) {
for (int i=1; i<=9; i++) {
ret += dfs(i, pos+1);
}
}
if (pos == 1) {
for (int i=cost; i<=9; i++) {
ret += dfs(cost*10+i,pos+1);
}
}
if (pos == 2) {
for (int i=cost/10; i<=9; i++) {
ret += dfs(cost*10+i, pos+1);
}
}
if (pos == 3) {
if (cost/100 == cost%10) {
for (int i=(cost/10)%10; i<=9; i++) {
ret += dfs(cost*10+i, pos+1);
}
}
else {
for (int i=cost/100+1; i<=9; i++) {
ret += dfs(cost*10+i, pos+1);
}
}
}
return ret;
}
int main() {
N=10000;
for (int i=0; i<4; i++) {
tmp *=10;
scanf("%d", &x);
tmp += x;
}
for (int i=0; i<4; i++) {
N = min(tmp, N);
tmp *=10;
tmp = (tmp%10000)+tmp/10000;
}
printf("%d\n", dfs(0, 0));
return 0;
}
