BOJ 2659 십자카드 문제


사용한 알고리즘

  • 완전탐색, DFS

알고리즘 설명

  • 입력받은 값에 시계수를 먼저 찾아낸다. 찾는 방법은 숫자를 한쪽으로 밀면서 최소 값을 찾는다.
  • 이 알고리즘에서는 왼쪽으로 밀었다. 예를 들면 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;
}



© 2020.08. by fbdp1202

Powered by theorydb