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

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

---

문제

• 주어진 N과 사칙연산만으로 주어진 number와 동일하게 만들 수 있는 최소 횟수

제한사항

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

풀이

단순하게 사칙연산 말고도 55 같이 숫자를 붙여서도 표현할 수 있는 걸 확인

예시 1

그리고 문제가 짧은만큼 문장 하나하나가 다 핵심이다.

• 최솟값이 8보다 크면 -1을 반환한다는 것은 반복하더라도 8번까지 확인한다.
• number가 1이상이라면 음수를 제외한다.
• 나누기 연산에서 0으로 나누면 무한이다.

 

연산을 한다면 각 값에 따라서 달라질 수 있다.

나눗셈와 뺄셈을 앞, 뒤에 따라 값이 달라질 수 있기에 기존에 n번의 연산을 했던 값을 이용해서 새로운 값을 만든다.

3번의 연산이 필요한 경우

 

3번의 연산을 했는데도 원하는 값이 안나왔을 때에는

아래와 같이 1번 연산한 값들과 3번 연산한 값들을 가지고 다시 연산하면 된다.

4번 연산하는 경우

 

코드

import Foundation

func solution(_ N:Int, _ number:Int) -> Int {
    var table = Array(repeating: Set<Int>(), count: 9)
    for n in 1...8 {
        for i in 1..<n {
            for f in table[i] {
                for b in table[n-i] {
                    table[n].insert(f + b)
                    table[n].insert(f * b)
                    if b != 0 { table[n].insert(f / b) }
                    if f >= b { table[n].insert(f - b) }
                }
            }
        }
        table[n].insert(Int(String(repeating: "\(N)", count: n))!)
        if table[n].contains(number) { return n }
    }
    
    return -1
}