[BOJ] 1527: 금민수의 개수

문제 소개

 

2020.03.22 기준,  실버 1티어 문제입니다.

 

원래 골드 5티어 문제였는데, 제가 실버 1을 부여하면서 바뀌었습니다.

(골드 5티어라고 하기엔 너무 쉬운 BFS 문제입니다.)

 

먼저, 문제를 풀 수 있는 아이디어부터 설명하고

코드를 설명하겠습니다.

 

 

문제 링크

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

1527번: 금민수의 개수

아이디어

문제에서 제한되는 범위는 1부터 1,000,000,000 까지입니다.

만약 이 범위를 일일이 탐색한다면, TLE가 뜰게 뻔합니다.

 

하지만 4와 7만을 이용해서 숫자를 탐색하는 DFS 혹은 BFS를 수행한다면 해봤다 O(2^k) (k<=7) 내로 끝납니다.

이정도 아이디어면 충분히 이문제를 해결할 수 있습니다.

코드

A,B = map(int,input().split())
Q = [4,7]
ans = 0
while len(Q) > 1:
    F = Q[0]
    Q.pop(0)

    if F <= B:
        if A<=F:
            ans +=1
        Q.append(F*10+4)
        Q.append(F*10+7)

print(ans)

위 코드는 BFS 탐색을 활용한 것이고, Q라는 이름의 리스트가 BFS 알고리즘에 필요한 queue를 대신하고 있습니다.

 

Rmx