문제
은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.
A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include<stdio.h>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
int num[10][(1 << 9) + 1];
int count(int a, int b) {
int ans = 0;
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= (1 << i); j++) {
if (a <= num[i][j] && num[i][j] <= b)ans++;
}
}
return ans;
}
int main()
{
num[1][1] = 4, num[1][2] = 7;
for (int i = 2; i <= 9; i++) {
for (int j = 1; j <= (1 << (i-1)); j++)
num[i][j] = num[i - 1][j] * 10 + 4;
for (int j = (1 << (i-1)) + 1; j <= (1 << (i )); j++)
num[i][j] = num[i - 1][j - (1 << (i-1))] * 10 + 7;
}
int a, b, ans = 0;
scanf("%d%d", &a, &b);
printf("%d\n", count(a, b));
return 0;
}
|
cs |
B의 최대값이 1,000,000,000 이므로 한 자리 금민수부터 아홉 자리 금민수까지 전부 구한 다음
a <= 금민수 <= b 인 금민수의 개수를 구하면 된다.
c++의 벡터를 쓰면 좀 더 편리할 거 같다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
백준 온라인 저지 (BOJ) 1806 부분합 (0) | 2020.09.21 |
---|---|
백준 온라인 저지 (BOJ) 13565 침투 (0) | 2020.09.21 |
백준 온라인 저지 (BOJ) 17427 약수의 합 2 (0) | 2020.09.21 |
백준 온라인 저지 (BOJ) 14716 현수막 (0) | 2020.09.20 |
백준 온라인 저지 (BOJ) 1490 자리수로 나누기 (0) | 2020.09.20 |