코딩테스트 연습 - N으로 표현

문제 해결 아이디어

이 문제를 DP로 접근할 때 f(i)를 무엇으로 정의할 때부터 정의해야 합니다.

🤔 f(i) = “i를 만들 수 있는 최소의 N의 갯수”

맨 처음 떠올리는 정의는 위의 정의일 것입니다. 하지만 위 처럼 f(i)를 정의하면 점화식을 만들기가 쉽지 않습니다.

일단 N으로 사칙연산을 할 수 있기 때문에 어떤 연산을 통해서 점화식을 만들어야 할 지 결정하기 어렵습니다. 아래 예시만 보더라도
2 = (5 / 5) + (5 / 5)의 경우 1, 1를 사용해서 덧셈을 사용하고 있고
12 = (55 + 5) / 5의 경우 60과 5를 사용해서 나눗셈을 사용하고 있습니다.

또한 큰 값 → 작은 값으로 점화식을 만들어야 할지 큰 값 → 작은 값으로 점화식을 만들어야 할지도 결정할 수 없습니다. 위의 예시를 그대로 사용하면
f(2) = f(1) + f(1)이고 f(12) = f(60) + f(5)입니다.

그리고 하나 더 number의 최댓값은 32000입니다. 이론상으로 f(32000)까지 구해야 한다는 것이죠… 아무리 DP가 빠르다고 하지만 부담되는 N입니다.

한마디로 하면 규칙이 없어 점화식을 만들 수 없는 i의 정의입니다.

🤔 f(i) = “i개의 N으로 만들 수 있는 숫자의 수”

자 그렇다면 어떻게 f(i)를 정의해야 할까요? 먼저 문제를 보면 약한 고리(?)가 하나 보입니다. N을 최대 8개까지만 사용할 수 있고 9개 이상의 경우 -1을 리턴하라고 합니다. 그렇다면 f(8)까지만 구하면 된다는 것입니다.

하지만 여기서 막히는 부분이 있습니다. f(i)를 “i개의 N으로 만들 수 있는 숫자의 수”로 정의하게 되면 f(i)로 f(i + 1)을 구할 수 있을까요?

(a개의 N으로 만들 수 있는 수)와 (i - a개의 N으로 만들 수 있는 수)를 사칙연산하면 (i개의 N으로 만들 수 있는 수)가 나오기는 합니다. 예를 들면 12 = (55 + 5) / 5 처럼요. (3개의 5로 만들 수 있는 수) / (1개의 5로 만들 수 있는 수) = (4개의 5로 만들 수 있는 수)입니다.

하지만 f(i)를 i개의 N으로 만들 수 있는 숫자의 “수"로 정의하면 위와 같은 점화식을 사용할 수 없습니다. 우리는 숫자가 아니라 실제로 “i개의 N으로 만들 수 있는 수” 그자체가 필요합니다.

🙌 f(i) = “i개의 N으로 만들 수 있는 수의 집합”

우리가 필요한 것은 바로 수 자체가 필요합니다. 중복을 제거하여 불필요한 연산을 하지 않기 위해서 집합을 사용합니다.

흔히 볼 수 있는 DP의 유형은 아닙니다. 우리는 보통 DP에 저장하는 것은 숫자가 많았지만 집합을 저장하지 말라는 법도 없습니다.

f(i)를 이렇게 정의하면 점화식을 아래처럼 만들 수 있게 됩니다.

f(i) = 
	f(1)과 f(i - 1)을 사칙연산한 수들의 집합
	+ f(2)와 f(i - 2)를 사칙연산한 수들의 집합
	+ ...
	+ f(i - 1)과 f(1)을 사칙연산한 수들의 집합

위 점화식에서 +는 합집합 연산을 의미합니다.

그리고 하나 더 주의할 점은 덧셈과 곱셈과는 달리 뺄셈과 나눗셈은 피연산자의 순서에 따라 값이 달라지므로

“f(1)과 f(i - 1)을 사칙연산한 수들의 집합”과 “f(i - 1)과 f(1)을 사칙연산한 수들의 집합”를 별개로 구해야 합니다.

코드

// 사칙 연산 정의
func add(_ x: Int, _ y: Int) -> Int {
    x + y
}

func substract(_ x: Int, _ y: Int) -> Int {
    x - y
}

func multiply(_ x: Int, _ y: Int) -> Int {
    x * y
}

func divide(_ x: Int, _ y: Int) -> Int {
    x / y
}

func solution(_ N:Int, _ number:Int) -> Int {
    // 두 집합에 있는 숫자들을 사칙연산한 값들을 구하는 함수
    func operateTwoSets(_ set1: Set<Int>, _ set2: Set<Int>, _ operation: (Int, Int) -> Int) -> Set<Int> {
        var result = Set<Int>()
        
        for x in set1 {
            for y in set2 {
                let number = operation(x, y)
                if number >= 1 && number <= 32000 {
                    result.insert(number)
                }
            }
        }
        
        return result
    }
    
    // 숫자 N을 n개 가지고 만들 수 있는 수를 구하는 함수
    func canMakeNumbers(_ n: Int) -> Set<Int> {
        var result = Set<Int>()
        let operations = [add, substract, multiply, divide]
        
        // 그냥 N을 n개 나열해서 쓴 수
        result.insert(Int(String(repeating: "\(N)", count: n))!)
        
        // 1일 때는 연산할 집합이 없으니까 리턴
        guard n != 1 else { return result }
        
        // set[1] ~ set[n - 1]에서 set[n - 1] ~ set[1]까지 집합을 각각 사칙연산한 결과를 result에 추가
        for i in 1...(n - 1) {
            for operation in operations {
                result = result.union(operateTwoSets(sets[i], sets[n - i], operation))
            }
        }
        return result
    }
    
    // sets[i] = i개의 N으로 만들 수 있는 수
    var sets = Array(repeating: Set<Int>(), count: 9)
    
    // 1 ~ 8개로 구할 수 있는 숫자들을 집합에 넣는다.
    for i in 1...8 {
        sets[i] = canMakeNumbers(i)
    }
    
    // number를 만들 수 있는 가장 적은 N을 찾는다
    for i in 1...8 {
        if sets[i].contains(number) {
            return i
        }
    }
    
    // 8개 이내의 N으로 number를 만들 수 없다면 -1을 리턴한다.
    return -1
}