백준 - 1105번 : 팔 (C++)

풀이 방법 : 그리디

처음엔 감이 안와서 완전 탐색에서 경우의 수를 줄이는 방향으로 생각해봤다.
완전탐색을 한다 치면 L부터 시작해서 R까지 증가시켜가면서 각각 8의 갯수를 세주면 될 것이다.

여기서 L과 R의 자릿수가 다른 경우를 생각해보았다. 만약 R이 자릿수가 L보다 크다면 무조건 8이 하나도 들어가지 않는 숫자가 최소 하나쯤은 있다. 이 경우 무조건 0을 출력해주면 된다.

결국 우리가 다뤄줘야할 것은 L과 R의 자릿수가 같은 경우가 될 것이다.
그럼 현재 L의 8의 갯수를 먼저 세 주는 것으로 시작해보자. 물론 L의 8 갯수가 0이라면 따져볼 필요도 없이 0을 출력해주면 될 것이다.

이후 L의 가장 뒷자리수부터 탐색해가면서 해당 자릿수가 8인 경우, 해당 자릿수에 8이 아닌 다른 숫자가 들어갈 수 있는지 확인해본다. 8이 들어간 자릿수를 그 다음 숫자인 9로 바꿔주고 이 자릿수의 뒷자리숫자들을 다 0으로 바꿔주면 8이 아닌 숫자중에 가장 작은 숫자가 될 것이다.
만약 이렇게 바꿔준 숫자를 TempL이라 치면 L <= TempL <= R 을 만족하면 8의 갯수를 줄여줄 수 있다는 의미이므로 앞서 구해둔 Count를 하나 줄여주면 된다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	string L, R;
	cin >> L >> R;

	int LLength = L.length();
	int RLength = R.length();

	if (RLength - LLength > 0)
	{
		cout << 0;
		return 0;
	}

	int LCnt = 0;

	for (int i = 0; i < LLength; ++i)
	{
		if (L[i] == '8')
			++LCnt;
	}
    
    if(LCnt == 0)
    {
		cout << 0;
		return 0;
	}
        

	string TempL = L;

	for (int i = LLength - 1; i >= 0; --i)
	{
		bool IsChanged = false;
		if (TempL[i] == '8')
		{
			IsChanged = true;
			TempL[i] = '9';

			for (int j = i + 1; j < LLength; ++j)
				TempL[j] = '0';
		}
		
		if (!IsChanged)
			continue;

		if (stoi(L) <= stoi(TempL) && stoi(TempL) <= stoi(R))
			--LCnt;
	}

	cout << LCnt;
}