[프로그래머스] N으로 표현

사용 언어: Kotlin

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=kotlin

프로그래머스

숫자 N과 number가 주어지면, N과 사칙연산만을 사용해서 number를 만들 수 있는지, 있다면 N을 사용한 최소 개수를 return한다.

N을 사용한 최소 개수가 8 초과이면, -1을 return한다.

 

N=5, number=12일때의 예시

12 = (55+5)/5

제한사항

1 <= N <= 9

1 <= number <= 32000

수식은 괄호, 사칙연산만 가능하다.

나눗셈은 나머지는 무시한다.

풀이

아래부터는 예제인 N=5, number=12를 예시로 들어 설명한다.

 

N을 1개 사용했을 때의 경우의 수는 아래와 같다.

count=1
5

 

N을 2개 사용했을 경우의 수는 아래와 같다.

count=2
55, (5+5), (5-5), (5*5), (5/5)

 

N을 3개 사용했을 경우의 수는 아래와 같다.

555, 
//(count = 3)일때의 경우

(55+5), (55-5), (55*5), (55/5),
((5+5)+5), ((5+5)-5), ((5+5)*5), ((5+5)/5),
...(위 줄이 +가 아닌 각각 -, *, /연산의 경우)
//(count = 2)일때의 경우와 (count = 1)일때의 경우의 사칙연산


(5+55), (5-55), (5*55), (5/55), 
(5+(5+5)), (5-(5+5)), (5*(5+5)), (5/(5+5)),
...(위 줄이 +가 아닌 각각 -, *, /연산의 경우)
//(count = 1)일때의 경우와 (count = 2)일때의 경우의 사칙연산

 

이런 풀이방식으로는 시간복잡도가 꽤 나오지 않나..? 싶었다.

근데, 문제의 제한사항으로 N을 8개까지만 쓸 수 있었다.

 

결국, N을 count개 사용하여 만들 수 있는 수의 경우의 수는 다음과 같다.

f(1) = N
f(count) = N을 count개 나열한 수 + (f(count-1) + f(1)) + (f(count-2) + f(2)) + ... + (f(1) + f(count-1))

 

dp[i]를 다음과 같이 정의한다.

dp[i] = N을 i개 썼을 때, 모든 경우의 연산 결과값의 집합

 

 

이후, 아래와 같이 정리할 수 있다.

calc[a,b] = a 집합과 b 집합의 각 원소에 대한 곱집합의 사칙연산의 결과 집합. (0으로 나누어지는 경우 제외)

dp[i] = {
	N을 i개만큼 일렬로 나열한 수 
	+ calc[dp[1], dp[n-1]]
	+ calc[dp[2], dp[n-2]]
	+ ... 
	+ calc[dp[n-1], dp[1]]
}

코드

fun solution(N: Int, num: Int): Int {
    val arr = Array<MutableSet<Int>>(9) { mutableSetOf() }
    for(i in 1..8) {
        arr[i].add(makeNum(N, i))
        for(j in 1 until i) {
            arr[j].forEach { first ->
                arr[i-j].forEach {  second ->
                    arr[i].add(first + second)
                    arr[i].add(first - second)
                    arr[i].add(first * second)
                    if(second != 0) arr[i].add(first / second)
                }
            }
        }
        if(arr[i].contains(num)) return i
    }
    return -1
}

fun makeNum(N: Int, count: Int): Int {
    return (0 until count).fold(0) { a, c ->
        a + 10.0.pow(c).toInt() * N
    }
}