백준 20164번: 홀릭 홀릭 호석

문제: https://www.acmicpc.net/problem/20164

문제 풀이

브루트 포스, 재귀

solve(num, count) = num을 문제 조건에 맞게 연산하는 함수, count는 이전 연산까지 센 홀수의 개수

min, max = 연산이 끝났을 때의 최솟값, 최댓값

각 자리의 숫자에서 홀수의 개수를 세어야 하므로 변수 temp, newCount를 만들고 각각 num, count를 저장해줌

temp가 0이 될때까지 반복하며 temp가 홀수라면 newCount 1 증가시키고 temp를 10으로 나눔

이러면 newCount에 현재까지 센 홀수의 개수가 저장됨

이후에 수가 한 자리인지, 두 자리인지, 세 자리 이상인지 확인해야 하므로 먼저 10으로 나눈 몫이 존재하는지 확인해 한 자리인지를 먼저 확인함

10으로 나눈 몫이 0이라면 한 자리이므로 더 이상 연산하지 못하기 때문에 현재까지 센 홀수의 개수 newCount를 각각 min, max와 비교해 최솟값, 최댓값을 갱신함

10으로 나눈 몫이 0이 아닐 때 100으로 나눈 몫이 0이라면 두 자리 수이므로 십의 자리 숫자 num / 10과 일의 자리 숫자 num % 10을 더한 값과 현재까지의 홀수의 개수 newCount를 인수로 solve를 재귀 호출함

100으로 나눈 몫도 0이 아니라면 세 자리 이상인 수이므로 수를 임의의 자리수에서 끊어서 3개의 수로 분할하고 더한 값을 다시 연산해야 함

자릿수에서 끊기 쉽게 num을 String으로 변환하고 subString을 이용해 분할한 이후에 toInt()로 다시 숫자로 변환함, 이때 i, j가 분할하는 첫째, 둘째 숫자가 끝나는 인덱스임

이렇게 만든 solve(num, count) 함수를 이용해 solve(N, 0)을 호출해 N을 조건에 맞게 연산시키면 min, max에 최솟값, 최댓값이 저장되므로 출력하면 정답

풀이 설명

연산을 할 때 자릿수가 거의 3분의 1로 줄어들고, N이 최대 9자리의 숫자기 때문에 모든 상황을 연산해도 충분한 시간 안에 계산할 수 있다.

연산을 하는 수가 한 자리거나 두 자리라면 연산이 무조건 정해지지만 세 자리 이상이라면 수를 어떻게 나누는지에 따라 나뉘기 때문에 이를 재귀함수로 만들어지는 수와 이전까지의 홀수의 개수를 받도록 처리하면 된다.

따라서 재귀 함수 solve(num, count)를 연산해야 하는 숫자 num, 이전까지 센 홀수의 갯수 count를 인수로 받도록 정의한다.

그렇게 num을 연산을 할 때 처음으로 해야 하는 것은 각 자리의 숫자에서 홀수의 갯수를 세는 것이다. 먼저 홀수인지 판별하는 것은 2로 나눈 나머지가 1인지 확인하는 것이다.

이 때 수를 2로 나눈 나머지는 항상 일의 자리의 숫자에만 영향을 받으므로 나머지가 1이면 일의 자리 숫자가 홀수라는 것이다. 그러므로 num을 2로 나눈 나머지를 확인하면 num의 일의 자리 숫자가 홀수인지 판별할 수 있다. 그 이후에 십의 자리 숫자를 홀수인지 확인하려면 num을 10으로 나눈 몫을 2로 나누어보면 된다.

그러므로 변수 temp에 num을 저장하고 temp를 0이 될때까지 10으로 나누면서 2로 나눈 나머지가 1인지 확인해 홀수의 갯수를 세면 된다. 이때 이전까지 센 홀수의 갯수가 count이므로 변수 newCount를 count로 초기화하고 temp를 2로 나눈 나머지가 1일때마다 1씩 증가시켜 갯수를 세면 된다.

이후에는 num이 한 자리, 두 자리, 세 자리 이상인지 구분해야 하는데 한 자리라면 10으로 나눈 몫이 0이어야 하고, 두 자리라면 100으로 나눈 몫이 0이어야 하고, 세 자리 이상이라면 100으로 나눈 몫이 0이 아니어야 하기 때문에 먼저 10으로 나눈 몫부터 확인하면 한 자리인지 두 자리 이상인지를 구분할 수 있다.

그러므로 10으로 나눈 몫을 확인해 한 자리라면 연산을 더 이상 진행할 수 없는 것이므로 현재까지 센 홀수의 갯수 newCount를 확인해 이 값이 최솟값이나 최댓값이 되는지 확인해야 한다. 그러므로 함수 밖에 정의해둔 min, max와 비교해 최솟값, 최댓값을 갱신하고 함수를 반환해 끝내면 된다.

10으로 나눈 몫이 0이 아니고 100으로 나눈 몫이 0이라면 두 자리의 숫자이므로 십의 자리 숫자 num / 10과 일의 자리 숫자 num % 10을 더한 값과 newCount를 인수로 solve() 함수를 재귀 호출하면 된다.

100으로 나눈 몫이 0이 아니라면 세 자리 이상인 숫자이므로 수를 임의로 3개의 부분으로 나누어야 한다. num을 String으로 변환하면 인덱스를 활용해 subString() 함수를 사용하면 쉽게 나눌 수 있다.

따라서 i를 첫 숫자가 끝나는 인덱스, j를 두 번째 숫자가 끝나는 인덱스로 만들면 두 번째 숫자, 세 번째 숫자는 항상 한 자리는 있어야 하므로 i는 s.length - 2보다 작아야 하고, j는 첫 번째 숫자보다 뒤쪽 인덱스에서 시작해야 하므로 i + 1부터 세 번째 숫자가 항상 한 자리는 있어야 하므로 s.length - 1보다 작아야 한다.

이에 맞게 subString() 함수를 이용해 3개의 숫자를 String으로 나누고 나면 다시 숫자로 변환해야 더할 수 있으므로 toInt() 함수를 이용해 변환한 이후에 더한 값과 newCount를 인수로 solve() 함수를 재귀 호출하면 된다.

그렇게 solve(num, count) 함수를 정의하면 문제를 풀기 위해 N과, 아직 홀수의 갯수를 세지 않았으므로 0을 인수로 함수를 실행하면 min, max에 각각 홀수의 갯수의 최솟값, 최댓값이 저장되므로 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run{
    nextToken()
    val N = nval.toInt()
    var min = Int.MAX_VALUE
    var max = Int.MIN_VALUE
    fun solve(num: Int, count: Int){
        var temp = num
        var newCount = count
        while(temp > 0){
            if(temp % 2 == 1){
                newCount++
            }
            temp /= 10
        }
        if(num / 10 == 0){
            min = minOf(min, newCount)
            max = maxOf(max, newCount)
            return
        } else if (num / 100 == 0){
            solve((num / 10) + (num % 10), newCount)
        } else {
            val s = num.toString()
            for(i in 0 until s.length - 2){
                for(j in i + 1 until s.length - 1){
                    solve(s.substring(0, i + 1).toInt() + s.substring(i + 1, j + 1).toInt() + s.substring(j + 1).toInt(), newCount)
                }
            }
        }
    }
    solve(N, 0)
    println("$min $max")
}