[알고리즘] 영화감독 숌 (백준 1436번)

1436번: 영화감독 숌

 브루트 포스 문제다. 시간복잡도를 생각해봤을 때, 정말 최대로 가정해봐도 1천만번 정도기에 단순히 1씩 증가시키는 연산으로도 충분히 풀만하다.

 

Solution

 666, 1666, 2666 이런식으로 1000단위로 증가하다가 6660, 6661과 같은 구간이 생길 것이다. 처음에는 이걸 일일이 구할까 하다가 브루트 포스 문제이니 좀 더 단순하게 생각해보자 해서 그냥 1씩 증가시켜서 나오는 수마다 세상의 종말 수인지를 검사해서 count를 증가시키는 방식으로 구했다.

 

 실제 N의 최대값인 10000번째 세상의 종말 수는 2666799이므로 약 3백만번, 거기다 문자열 검사를 하는 시간으로 고려해보면 최대 7글자라고 봤을 때, 약 2천만번 정도 될 듯 하다.

 

fun solution() {

    var N = readLine()!!.toInt()

    var result = 665
    var count = 0

    while(count < N)
    {
        result++
        if(isRight(result))
            count++
    }
    print(result)

}

//세상의 종말 수가 맞는지 확인
fun isRight(current : Int) : Boolean
{
    var str = current.toString()

    var count = 0

    for(i in 0 until str.length)
    {
        if(str[i] == '6')
            count++
        else
            count = 0

        if(count == 3)
            return true
    }
    return false
}


fun main() {
    solution()
}