[C++] 백준 알고리즘 1527번 (금민수의 개수)

문제

---

이번에 다뤄볼 문제는 1527번 문제 '금민수의 개수'입니다.

금민수의 개수 문제에서 연습해야하는 key-point는 큐입니다.

 

큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로,

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다.

 

A와B사이에 존재하는 모든 금민수의 개수를 구하는 문제 입니다.
해당 문제의 test case 값 범위가 1,000,000,000이기 때문에 변수를 선언알때
long long int 를 활용하였습니다.
큐에 기본 금민수인 4 와 7을 초기값으로 넣어놓고
이들 각각의 자리수를 한 자리씩 올려주며 4,7을 더해줍니다. 그 후 바꾼 수를 큐에 넣습니다.
ex) 4,7 -> 44,47,74,77 -> 444,447,474,477,744,747,774,777 ...
이런 식의 수가 주어진 범위 내에 존재한다면 kms_count값을 하나씩 증가시켜줍니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include <iostream>
using namespace std;
 
int q[100000];
int front = 0, rear = 0;
 
 
int main() {
 
    long long int n = 0, m = 0;
    long long int kms = 0;
    int kms_count = 0;
 
    cin >> m >> n;
 
    q[rear++] = 4; q[rear++] = 7;
 
 
    while (front != rear) {
        kms = q[front++];
        if (kms >= m && kms <= n) kms_count++;
        if (kms * 10 + 4 <= n) {
            q[rear++] = kms * 10 + 4;
        }
        if (kms * 10 + 7 <= n) {
            q[rear++] = kms * 10 + 7;
        }
    }
    cout << kms_count << endl;
 
    return 0;
}