[BOJ] 1105 - 팔

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

BOJ - 팔

문제 유형: 수학, 그리디

문제 난이도: Silver I

시간 제한: 1초

메모리 제한: 512MB

 

문제

L과 R이 주어진다. 이때, L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.

 

풀이

 

이 문제에서 중요한 것은, 상위 자릿수에서 얼마나 연속적으로 수들이 일치하는지와 그 사이에 8이 얼마나 있는지가 중요하다.

입력받은 수를 자릿수별로 잘라서, 최상위 자릿수부터 비교한다.

만약 최상위 자릿수가 둘다 8이라면, 정답의 개수를 1 늘린다.

만약 최상위 자릿수가 다르면, 끝이다. 이후로는 제약이 없으므로 8이 아닌 수를 넣으면 된다. 즉, 비교를 탈출하고 정답을 반환해주면 된다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  int l, r;
  cin >> l >> r;
  int max_radix = max(log10(l), log10(r)) + 1;

  vector<int> lvec(max_radix, 0);
  vector<int> rvec(max_radix, 0);

  for (int i = 0; i < max_radix; ++i) {
    int ldigit = l % 10;
    int rdigit = r % 10;
    lvec[i] = ldigit;
    rvec[i] = rdigit;

    l /= 10;
    r /= 10;
  }

  int ans = 0;
  for (int i = max_radix - 1; i >= 0; --i) {
    if (lvec[i] != rvec[i])
      break;
    if (lvec[i] == rvec[i] && lvec[i] == 8)
      ans++;
  }
  cout << ans << "\n";

  return 0;
}