[백준] 16968 차량번호판 (c++)

https://www.acmicpc.net/problem/16968

16968번: 차량 번호판 1

 

처음 작성한 로직

1. d 의 갯수와 c 의 갯수를 구한다.

2-1. 0~9 의 숫자에서 d 길이를 가진 중복순열을 구한다.

2-2. a~z 에서 c의 길이를 가진 중복순열을 구한다.

3. 뽑은 2-1. 의 결과와 2-2. 의 결과를 처음 인풋으로 받은 순서대로 배치하여 하나의 번호판을 구한다.

4. 구한 번호판이 같은 문자 또는 숫자가 연속해서 나타나는 지 확인한다.

5. 연속되지 않는다면 벡터에 집어넣는다.

6. 벡터내에 중복 요소들을 제거한 후, 벡터의 길이를 출력한다.

이 방식대로 구현했을 때, 성공하기는 하지만, 메모리가 어마무시하다...ㅎ

각 값들을 구하는 문제라면 이 방법이 좋을 수도 있겠지만 우리는 경우의 수만 필요하다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>

using namespace std;
int d, c;
char input[5];
int visit[10];
char visit2[26];
int number[10] = {0,1,2,3,4,5,6,7,8,9};
char alphabet[26];

vector <string> words;

void checker() {
	vector <int> d_c;
	for(int i=0; i<10; i++)
		if(visit[i] != -1) {
			d_c.push_back(visit[i]);
		}

	vector <char> c_c;
	for(int i=0; i<26; i++)
		if(visit2[i] != 0){
			c_c.push_back(visit2[i]);
		}

	int c_idx = 0; int d_idx = 0;

	string word = "";
	for(int i=0; i<int(strlen(input)); i++) {
		if(input[i] == 'd') {
			word += d_c[d_idx++];
		}
		else if(input[i] == 'c')
			word +=  c_c[c_idx++];
	}

	bool dup = false;
	for(int i=0; i<int(word.size())-1; i++)
		if(word[i] == word[i+1]) {
			dup = true;
			break;
		}

	if(dup == false)
		words.push_back(word);

}

void dfs2(int cnt, int target) {
	if(cnt == target) {
		for(int i=0; i<target; i++) {
			// 순서대로 만들기
			checker();

		}
		return;
	}
	for(int i=0; i<26; i++) {
		visit2[cnt] = alphabet[i];
		dfs2(cnt+1, target);
		visit2[cnt] = 0;
	}
}

void dfs(int cnt, int target) {
	if(cnt == target) {
		
		if(c > 0) {
			//알파벳 뽑기
			dfs2(0, c);
		}
		else
			checker();
		return;
		
	}
	for(int i=0; i<10; i++) {
		visit[cnt] = number[i];
		dfs(cnt+1, target);
		visit[cnt] = -1;
	}
}

int main() {

	cin >> input;

	for(char i=0; i<26; i++) {
		alphabet[i] = 'a'+i;
	}

	for(int i=0; i<int(strlen(input)); i++) {
		if(input[i] == 'd')
			d++;
		else if(input[i] == 'c')
			c++;
	}

	for(int i=0; i<10; i++)
		visit[i] = -1;

	for(int i=0; i<26; i++)
		visit2[i] = 0;
	
	if(d!= 0)
		dfs(0, d);
	else if(d == 0 && c > 0)
		dfs2(0, c);

	else if (d == 0 && c== 0){
		printf("1");
		exit(0);
	}

	// 중복제거
	sort(words.begin(), words.end());
	words.erase(unique(words.begin(), words.end()), words.end());

	printf("%lu\n", words.size());

}

다른 사람들의 코드를 보고 다시 구현을 해보았다.

경우의 수만 보면 되는 것이니까 실제로 값을 구하지 않아도 된다.

dd, cc 의 경우 연속이 될 수 있기 때문에 

 

dd ) 두번째 d 에 올수 있는 경우의 수는 9

cd) d 에 올 수 있는 경우의 수는 10

cc ) 두번째 c 에 올수 있는 경우의 수는 25

dc) c 에 올 수 있는 경우의 수는 26

 

각 자리의 경우의 수들을 곱해주면 총 경우의 수를 얻어낼 수 있다.

#include <iostream>
#include <cstring>

using namespace std;

int main() {

	string form = "";
	cin >> form;

	int res = 0;

	if(form[0] == 'd')
		res = 10;
	else if(form[0] == 'c')
		res = 26;

	for(int i=1; i< form.length(); i++) {

		if(form[i] == 'd') {
			// compare with before value
			if(form[i-1] == 'd')
				res *= 9;
			else
				res *= 10;

		}
		else if(form[i] == 'c') {
			// compare with before value
			if(form[i-1] == 'c')
				res *= 25;
			else
				res *= 26;
		}
	}

	printf("%d\n", res);

	return 0;
}