[백준/Python] 1527. 금민수의 개수

 

 

 

1. 백준 1527. 금민수의 개수 (실1) 

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

1527번: 금민수의 개수

 

풀이

 

CODE

import sys

input = sys.stdin.readline

a, b = map(int, input().split())

cnt = 0
len_a = len(str(a))
len_b = len(str(b))


def backtracking(num, length):
    global cnt
    if len(num) == length:
        if a <= int(''.join(map(str, num))) <= b:
            cnt += 1
        return

    for each in [4, 7]:
        num.append(each)
        backtracking(num, length)
        num.pop()


for i in range(len_a, len_b + 1):
    backtracking([], i)

print(cnt)

• 이번 알고리즘 스터디 문제들 왜이렇게 어려운가에 대하여...
• 완전 범위 비교는 당연히 시간초과가 되고, 범위 내에서 4, 7로 이루어진 숫자를 만들고 해당 내용에 대한 정수를 범위 비교하여 cnt 수를 업데이트 했다.