백준 1527 금민수의 개수 Kotlin (완전 탐색)

문제 출처 : https://www.acmicpc.net/problem/1527

1527번: 금민수의 개수

문제

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력한다.

알고리즘 분류

• 브루트포스 알고리즘

풀이

s가 20

e가 9000으로 주어졌다고 생각해 보자.

s.length = 2

e.length = 4

길이가 2 이상 4 이하인 금민수(4,7로만 이루어진 수)를 모두 구하고 거기서 s <= 금민수 && 금민수 <= e 인 금민수의 개수를 구하면 끝

본인은 4로 시작하는 수와 7로 시작하는 수를 시작으로 돌려서 해당하는 수들을 모두 구해줬다.

문제가 간단한 만큼 풀이도 간단했던 문제.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()
var answer = 0
fun subset(result: Long, len: Int, s: Int, e: Int, sLen: Int, eLen: Int) {
    if (len > eLen) return
    if (len >= sLen) {
        if (result in s..e) answer++
    }
    subset(result * 10 + 4, len + 1, s, e, sLen, eLen)
    subset(result * 10 + 7, len + 1, s, e, sLen, eLen)
}

fun main() = with(System.out.bufferedWriter()) {

    val (s, e) = getIntList()
    subset(4, 1, s, e, s.toString().length, e.toString().length)
    subset(7, 1, s, e, s.toString().length, e.toString().length)
    write("$answer")
    close()
}