[python] 1527 - 금민수의 개수

1527번: 금민수의 개수 (acmicpc.net)

1527번: 금민수의 개수

 

문제 자체는..간단하지만

백퍼 시간초과 걸리겠다 생각한 문제였다.

첫 접근방식은 범위내의 모든 수를 검사했더니 역시나 시간초과가 떴고

다른 접근 방법으로 문제를 풀이하였다.

 

범위가 넓기 때문에 모든 수를 검사하기 보다

자릿수를 계산하여 4와 7만 들어간 수들의 리스트를 생성한다.

그리고 그 수들이 주어진 a와 b의 범위내에 들어가는 수인지를 판단한다.

 

역으로 생각하면 검사해야 할 데이터가 확 줄어들기 때문에 시간초과에 걸리지 않고

해결 가능하다!

 

# 1527 금민수의 개수
import sys
from itertools import product

input = sys.stdin.readline

a,b = map(int, input().split())
ax = len(str(a))
bx = len(str(b))

cnt=0
for i in range(ax, bx+1):
    lst= list(product(["4","7"], repeat=i))
    for x in lst:
        tmp=int(''.join(list(x)))
        if a<=tmp <=b:
            cnt+=1
print(cnt)

 

 

 

 

 

* 모든 코드는 github에서 관리합니다.  seinShin (SEIN SHIN) (github.com)

seinShin - Overview