[BOJ] 1105_팔

팔

문제 링크: https://www.acmicpc.net/problem/1105

1105번: 팔

일반적인 완전 탐색으로 l부터 r까지의 수를 모두 찾게되면 시간 초과가 나온다.
그래서 규칙을 찾을 필요가 있었다.
두 수가 주어졌을 때 8의 수는 어떤 수와 가장 연관이 있는가?
예제를 보았을 때 앞자리 수와 연관성을 띈다.

1. 일단, 수를 비교할 때 자릿수가 차이가 난다면 8의 최소 개수는 0이다.
   이유는 88과 888 사이에 최소 개수는 0인 이유가 된다.
   최소 100이라는 숫자가 존재하기 때문이다.

2. 그리고 8188과 8288 사이에 8200이라는 수가 존재한다.
   같은 자리의 수를 비교할 때 그 수가 다르다면 '00'이라는 8이 아닌 수가 존재할 수 밖에 없다.

3. 하지만 이때 맨 앞자리 수가 같고 8이므로 적어도 8이 1 번 나올수 밖에 없다.

이를 토대로 설명하자면,
L과 R의 자릿수가 차이가 난다면 무조건 10^n이라는 숫자가 존재하므로 최소 개수는 0이다.

그렇지 않을경우 앞자리 부터 L과 R을 비교하되, 같은 8일 경우 최소 N번의 8이 나온다.
그리고, 비교하던 도중 값이 다를 경우 최소 '00'이라는 수가 존재하므로 8이 존재하지 않을 가능성이 있다.

• 정답 코드

    #include<iostream>
    using namespace std;
  
    bool eightCount(char a, char b) {
        if (a == b)
            if (a == '8')
                return true;
        return false;
    }
  
    int main() {
        string L, R;
        cin >> L >> R;
        string l = " ", r = " ";
        l.append(L);
        r.append(R);
  
        if (l.length() != r.length())
            cout << 0 << endl;
        else {
            int minCount = 0;
  
            for (int i = 1; i <= l.length(); i++) 
                if (l[i] != r[i])
                    break;
                else if (eightCount(l[i], r[i]))
                    minCount++;
  
            cout << minCount << endl;
        }
        return 0;
    }