[BOJ]16968번: 차량 번호판 1 (c++)

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

16968번: 차량 번호판 1

 

방법 1: 그리디

#include <iostream>

using namespace std;

int get_next(char bfr, char now)
{
	int next = 0;
	if (now == 'c')
	{
		next = 26;
	}
	else
	{
		next = 10;
	}

	// 앞 문자와 중복되는 경우 제외
	if (bfr == now)
	{
		--next;
	}

	return next;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	string format;
	cin >> format;

	// 각 자리의 경우의 수를 구해서 곱하기
	int total = get_next(0, format[0]);
	for (int i = 1; i < format.size(); ++i)
	{
		total *= get_next(format[i - 1], format[i]);
	}

	cout << total;

	return 0;
}

 

 

방법 2: 브루트포스

#include <iostream>

using namespace std;

int dfs(string &format, int idx, int bf)
{
	if (format.size() == idx)
	{
		return 1;
	}

	/*
		문자 형식 : a ~ z
		숫자 형식 : 0 ~ 9
	*/
	int strt = (format[idx] == 'c' ? 'a' : '0');
	int end = (format[idx] == 'c' ? 'z' : '9');

	int total = 0;
	for (char i = strt; i <= end; ++i)
	{
		// 앞문자와 중복되지 않으면 경우의 수 카운팅
		if (i != bf)
		{
			total += dfs(format, idx + 1, i);
		}
	}
	return total;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	string format;
	cin >> format;

	// dfs 브루트포스로 가능한 모든 경우의 수 구하기
	cout << dfs(format, 0, ' ');


	return 0;
}

 

 

방법 1(그리디)은 앞의 형식문자와 뒤의 형식문자가 같을 경우, 곱해주는 경우의 수를 1 빼준다.

방법 2(브루트 포스)는 앞의 문자와 뒤의 문자가 같을 경우, 해당 경우를 카운팅하지 않는다.

 

브루트 포스가 가능한 이유는 최대 경우의 수가 26^4=456,976 밖에 되지 않기 때문이다.

물론 이 문제는 브루트 포스로 푸는 것이 매우 비효율적이지만, 연습삼아!