[BOJ] 1105번_팔_그리디 (C++)

[문제]

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

L과 R이 주어질 때, L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어 있는 8의 개수를 구하는 문제이다.

[사용 알고리즘]

그리디

[풀이 핵심]

• 이 문제의 핵심은 L과 R의 자리수가 다를 때, L과 R의 자리수가 같을 때로 나누어 생각하는 것이다.
• <L과 R의 자리수가 다를 때>
  L과 R의 자리수가 다르면 답은 무조건 0이다. 예를 들어 극단적으로 1과 1000을 생각해보자. 1~1000 사이의 수 중에서 8이 안들어 있는 숫자는 매우 많다. 그 수들 중 하나를 고르면 되므로 무조건 답은 0이 된다.
• <L과 R의 자리수가 같을 때>
  그리디한 방법으로 앞자리부터 L과 R이 같으면 그 값을 vector에 넣어주고, 달라질 시 break해준다. 왜냐하면 값이 다른 순간부터 8이 아닌 수를 넣을 수 있기 때문이다. 예를 들어 883844와 883888을 생각해보자. 8838까지 똑같고 뒤에 2자리 수만 다른데 이때 44~88사이에 8이 안들어 있는 숫자는 많기 때문에 그 수를 고르면 된다.
  그리고 vector안에 들어있는 수 중 8의 개수를 세어주면 그게 정답이다.

[코드]

//boj1105번_팔_그리디 알고리즘

#include<iostream>
#include<vector>

using namespace std;

int main() {
	string L, R;
	cin >> L >> R;

	vector<char> v;

	if (L.size() != R.size()) {
		cout << 0;
		return 0;
	}
	else {
		for (int i = 0; i < L.size(); i++) {
			if (L[i] == R[i]) {
				v.push_back(L[i]);
			}
			else {
				break;
			}
		}
	}
	
	int result = 0;

	for (int i = 0; i < v.size(); i++) {
		if (v[i] == '8') {
			result++;
		}
	}

	cout << result;

	return 0;
}