[LeetCode] 2310. Sum of Numbers With Units Digit K

Link : 2310. Sum of Numbers With Units Digit K

문제 정의

Given two integers num and k, consider a set of positive integers with the following properties:

• The units digit of each integer is k.

• The sum of the integers is num.

Return the minimum possible size of such a set, or -1 if no such set exists.

Note:

• The set can contain multiple instances of the same integer, and the sum of an empty set is considered 0.

• The units digit of a number is the rightmost digit of the number

문제 한문장 요약

일의 자리수가 k인 최소 수열의 합이 num이 될 때, 해당 수열의 최소 개수를 구해라

문제 분석

i = 우리가 구하고자 하는 최소 수열의 개수

$$num = k + (10 × 1 + k) + (10 × 2+ k) + …$$

$$num = k * i + (10 + 20 + 30 + … + 10 * (i - 1))$$

$$(num - k * i) \equiv 0 \bmod 10$$

우리가 구하고자 하는 최수 수열의 개수는 명확하게 정해져있고 수학공식을 통해서 num을 확인할 수 있는 확인 공식이 만들어졌기 때문에 이제 전체탐색을 통해서 값의 결과를 찾을 수 있습니다.

다행히 문제에서 제공되는 입력 값의 범위가 0 <= num <= 3000 이기 때문에 전체탐색을 해도 무리가 없을 것으로 판단됩니다.

해결 방법

1차 시도

처음에는 문제를 자세하게 분석하지 않고 다음과 같이 시도를 했습니다.

1. 일의 자리가 k인 모든 수를 뽑는다

2. 뽑은 수를 이용하여 dfs로 탐색한다

import kotlin.math.min


class Solution {
    var answer: Int = Int.MAX_VALUE

    fun minimumNumbers(num: Int, k: Int): Int {
        if (num == 0) return 0

        val list = mutableListOf<Int>()

        for (i in 1..num) {
            val mod = i % 10

            if (mod == k) {
                list.add(i)
            }
        }

        if (list.isEmpty() && num < k) return -1
        if (list.isEmpty()) return 0

        val visited = BooleanArray(list.size) { false }

        dfs(visited, list, num, 0)

        return if (Int.MAX_VALUE == answer) -1 else answer
    }

    fun dfs(visited: BooleanArray, list: List<Int>, target: Int, sum: Int) {
        for (i in list.indices) {
            if (visited[i]) continue
            visited[i] = true
            val curSum = sum + list[i]

            if (target == curSum) {
                answer = min(visited.count { it }, answer)
                visited[i] = false
                break // 여기서 종료
            } else {
                dfs(visited, list, target, curSum)
                visited[i] = false
            }
        }
    }
}

fun main() {
    val solution = Solution()
    val answer = solution.minimumNumbers(58, 9)
    println(answer)
}

하지만 해당 코드는 정답이 되지 못했습니다.

왜냐하면 해당 문제를 풀 수 있는지 없는지를 정확하게 판단하지 못했고 문제 풀이의 복잡성이 증가하여 어느 순간부터 코드를 수정할 수 없는 수준까지 이르렀기 때문입니다.

2차 시도

class Solution {
    fun minimumNumbers(num: Int, k: Int): Int {
        if (num == 0) return 0

        for (i in 1..10) {
            val total = i * k 
            if (total > num) continue
            if ((num - total) % 10 == 0) {
                return i
            }
        }

        return -1
    }
}

이번에는 문제를 분석한 것을 바탕으로 수식으로 풀어보았습니다

$$(num - k * i) \equiv 0 \bmod 10$$

느낀점

코드를 작성하면서 문제만 읽고 그대로 푸는 것이 아닌 수학적으로 분석하고 새로운 공식을 도출하는 부분이 해당 문제의 가장 어려운 부분이 아닐까 싶습니다. 해답 자체는 굉장히 짧고 단순하지만 코드하나하나에 수학적인 이유가 들어가 있는 부분은 이 문제를 얼마나 많이 고민하고 깔끔하고 정리하냐에 따라서 확실히 달라지는 부분으로 보입니다.