[python] 1105, 팔 : 수학, 그리디

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

1105번: 팔

 

[문제] 

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

 

[입력]

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

 

[출력]

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

 

[예제]

 

[풀이]

💡 문제 요약 : l과 r 사이 8이 가장 적게 들어있는 수의 8 개수를 구하기

💡 풀이 포인트

( 1 ) 두 수의 길이가 다르면 무조건 8이 들어가지 않는 수가 존재한다 (Ex. 100 & 1000) >> 0

( 2 ) 두 수의 길이가 같을 때는 큰 자릿수부터 확인해본다 >> 요기가 포인트 !

 

두 수의 길이가 같을 때 큰 자릿수부터 확인해야 하는 이유는 큰 자릿수에서 동일한 값을 가지고 & 8을 가지면 이때의 8의 개수는 무조건 포함되는 값이기 때문이다. 그리고, 큰 자릿수부터 확인하다가 동일한 값을 가지지 않는다면 그 즉시 반복문을 멈추고 결과를 반환한다.

 

예시를 통해 이해하면 더 쉽다.

Ex1. 8808 ~ 8818 : 8808, 8809, 8810 ... 8818 >> 88__이며, 천의자리, 백의자리 88만 고정된 8의 개수

Ex2. 4011 ~ 4122 : 4확인 > 0 != 1 반복문 break > answer = 0

l, r = map(str, input().split())

if len(l) != len(r):
  print(0)
else:
  answer = 0
  for i in range(len(r)):
    if l[i] == r[i]:
      if l[i] == '8':
        answer += 1
    else:
      break;

   print(answer)