백준 2287 - 모노디지털 표현 - swift

 

https://www.acmicpc.net/problem/2287

2287번: 모노디지털 표현

 

 

 

 

 

조합과 dp를 이용한다. 

 

사칙연산으로 경우의수를 고려하다보면 골치아파진다. 

물론 사칙연산으로 경우의수를 고려하긴해야하는데,  이는 4가지경우의수로만 한정짓고, 

K가 몇개사용됐는지를 중점으로 경우의수로 고민하면 풀린다. 

 

K는 최대 8개까지사용할수있다고했다. 

 

또한 문제에서 K가 연속으로 붙어있는경우도 존재한다.

그러므로, K가 1개, 2개, 3개...8개 사용했을때 모든경우의수를 구해본다. 

 

즉, 2개사용됐을때는,

KK ,

K + K ,

K - K ,

K*K ,

K/K  이렇게 존재하겠다. 

 

3개사용됐을때는?

KKK, 

K + K + K ,

K + K - K ... 이렇게 생각하기보다는 

 

arr[ i ] = K가 i개 사용됐을때 모든 사칙연산을 고려하여 나올수있는 숫자들의 집합으로 정의한다. 

그러므로, 3개가 사용됐을때는 아래와같이 모든 집합들에 대해 사칙연산을 구한다. 

arr[ 1 ] + arr[ 2 ] ,

arr[ 1 ] - arr[ 2 ] , 

arr[ 1 ] * arr[ 2 ] ,

arr[ 1 ] / arr[ 2 ] 로 구한다. 

 

즉 , arr [ 1 ] , arr [ 2 ] 

arr [ 2 ] , arr[ 1 ] 로구할수있다. 

 

테스트하는 숫자들은 최대 천개이므로, 각 숫자들에대해서 매번 시행하기보다는, 

K를 공통적으로 사용하기때문에, 우선 1...8까지의 K를 모두 구한다음에 

테스트숫자들이 있는지를 확인한다. 

 

let K = Int(readLine()!)!
let N = Int(readLine()!)!
var ans = Array(repeating: "NO", count: N)
var dict = [Int:Int]()
for i in 0..<N {
    let X = Int(readLine()!)!
    dict[X] = i
}

var arr = Array(repeating: Set<Int>(), count: 9)

var x = 0
var y = 1
for i in 1...8 {
    x += y*K
    arr[i].insert(x)
    y *= 10
}

for i in 2...8 {
    for j in 1..<i {
        arr[j].forEach { x in
            arr[i-j].forEach { y in
                arr[i].insert(x+y)
                arr[i].insert(x-y)
                arr[i].insert(x*y)
                if y > 0 {
                    arr[i].insert(x/y)
                }
            }
        }
    }
}

for i in 1...8 {
    for j in arr[i] {
        if let x = dict[j] {
            dict.removeValue(forKey: j)
            ans[x] = String(i)
        }
    }
}
ans.forEach{ print($0)}