BOJ | 1105 - 팔 (python)

💪 백준 1105번 팔 파이썬

---

 

✏️ 문제

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

 

 

 

💡 해결방법

숫자의 자릿수가 다른 것은 8이 꼭 들어갈 확률이 없으므로 (89, 800 과 같이 자릿수가 다른 것) 고려하지 않았다.

-> 숫자의 자릿수가 같은 것만 고려했다! (100, 200 / 80, 88 과 같은 수)

 

가장 큰 자릿수부터 비교하면서 R과 L 모두 8이면 무조건 8이 들어갈 수 밖에 없다.

하지만 중간에 자릿수가 차이나는 수가 들어오게 된다면 그 이후부터는 8이 꼭 들어오지 않아도 되기 그 뒤는 더 이상 비교하지 않아도 된다.

 

반례로 88008 88018 을 비교한다고 생각하자.

앞부터 88은 무조건 들어가야 하기 때문에 2번은 필수지만, 이후부터는 0과 1이 차이가 나므로 그 뒤는 더 비교하지 않아도 된다.

맨 마지막에 8이 들어간다고 해서 굳이 비교하지 않아도 된다 !!

 

🤓 깨달은 것

반례를 계속 생각했는데 위에 적은 반례를 생각하지 못해서 틀렸었다. 정답이라고 확신했는데 ..

그리디인 문제 잘 파악하고 반례 조건도 잘 생각하기 !

 

 

👩🏻‍💻 소스코드

import sys
input = sys.stdin.readline

l, r = map(str, input().split())
answer = 0
if len(l) != len(r):
    answer = 0
else:
    for i in range(len(l)):
        if int(l[i]) == 8 and int(r[i]) == 8:
            answer += 1
        elif abs(int(l[i])-int(r[i])) > 0:
            break

print(answer)

---