CodeDrive

문제:

은민이는 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,000,000,000로 엄청 크게 주어졌기 때문에 A~B 사이의 수가 4와 7로 이루어져있는지 탐색하는 것은 시간초과가 발생할 것이다. 따라서4와 7로 구성된 숫자를 만들면서 이 숫자가 A~B 사이에 있는지 확인하도록 한다.

 A와 B가 큰 수로 주어질 수도 있기 때문에 깊이라는 개념을 사용해서 최대한 탐색할 수 있도록 했다. 깊이는 상한값으로 인해 최대 9까지 가능하다. 깊이라는 개념이 추가되었기 때문에 깊이우선탐색을 사용해서 값을 만들어내도록 한다.

 생성된 값이 주어진 범위 안에 들어 있으면 count를 1 올려주고 상한 값을 넘어가면 더 빠른 탐색을 위해서 0을 반환하도록 했다. 하한값에 보다 작은 값에 대해서는 조건이 없는데, 그 이유는 앞서 말했던 A와 B가 큰 수로 주어졌을 때, 그 범위 내까지는 이동하도록 하기 위함이다.

문제링크:

www.acmicpc.net/problem/1527