문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한 사항

  • N은 1 이상 9 이하입니다.
  • number는 1 이상 32,000 이하입니다.
  • 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
  • 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N number return
5 12 4
2 11 3

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

문제 풀이

처음 시도에는 dp[i-1] 번째에 N 을 단순히 사칙연산을 적용시켰다. 괄호를 생각하지 못했다 괄호로 포함된 숫자 라는것은 괄호안에 포함된 N의 갯수만큼 만을 따로 빼와서 계산 해주어야 한다.

예를 들어 dp[6]을 구하고자 하면.. N = 5, 5를 7번 써서 만들수 있는수

  • dp[5] 와 dp[0] (5가 6번 쓰인 경우의 수 * 1번 쓰인 경우의 수)
  • dp[4] 와 dp[1] (5가 5번 쓰인 경우의 수 * 2번 쓰인 경우의 수)
  • dp[3] 와 dp[2] (5가 4번 쓰인 경우의 수 * 3번 쓰인 경우의 수)

를 구해줘야 한다.


import Foundation

func makeContinuousNumber(number: Int, count: Int) -> Int {
    var continuousNumber = 0
    
    for i in 0..<count {
        continuousNumber += Int(pow(10.0, Double(i))) * number
    }
    
    return continuousNumber
}

func solution(_ N:Int, _ number:Int) -> Int {
    if number == N { return 1 }
    
    var dp: [[Int]] = Array(repeating: [], count: 8)
    dp[0] = [N]
    
    for i in 1...7 {
        dp[i] += [makeContinuousNumber(number: N, count: i+1)]

        for j in 0..<i {
            for op1 in dp[j] {
                for op2 in dp[i-j-1] {
                    dp[i] += [op1 + op2, op1 - op2, op1 * op2, op1 / op2]
                }
            }
        }
        
        dp[i] = Array(Set(dp[i])).filter{ $0>0 && $0<=32000 }

        if dp[i].contains(number) { return i + 1 }
    }

    return -1
}

참고 : https://programmers.co.kr/learn/courses/30/lessons/42895?language=swift