[프로그래머스] 동적계획법(DynamicProgramming) - N으로 표현 (Swift 풀이)

programmers.co.kr/learn/courses/30/lessons/42895

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

 

정말 정말 오래 걸린 문제....

아이디어를 떠올리는 것 조차 하기 힘들었다.

 

1부터 순서대로 적어보자

처음에는 N=5인 경우, 모든 숫자 조합을 차례로 적어보려 했다.

N = 5

1 = 5/5
2 = (5+5)/5
3 = (5+5+5)/5
4 = 5 - 5/5
...

근데 아무리 이렇게 적어봐도 규칙이 보이지도 않고, 내가 적은 표현 방식보다 더 적은 개수로 표현 가능한지 판단하기도 힘들었다.

확실한건,, 저렇게 풀면 안된다는거,,,,,,, 완전 느껴버림

 

사용할 개수 순서대로 적어보자

그럼 숫자 순서대로 적어보는 것이 아니라, 사용할 N의 개수 순서대로 적어보는 것은 어떨까??

일단, count개를 사용하는 방식으로는 count-1개에서 1개를 더 사용하면 되기 때문에

count-1개에서 가능한 숫자에 /,-,+,* 를 하나씩 더해서 새로운 숫자를 도출해보았다.

N = 5

<1개 사용>
5

<2개 사용>
55
5/5 = 1
5-5 = 0   --- 1 이상인 수만 유효하다
5+5 = 10
5*5 = 25

<3개 사용>
555
5/5/5 = 0    --- 1 이상인 수만 유효하다
5/5-5 = -4  --- 1 이상인 수만 유효하다
5/5+5 = 6
5/5*5 = 5    --- 1개만 사용해도 5를 만들 수 있다.
5-5-5 = -5  --- 1 이상인 수만 유효하다
5-5/5 = 4
.....

 

따라서, count개를 사용하는 숫자의 목록은

• count번 반복한 수 ex) N=5, count=3 일 때 555
• count-1개를 사용한 숫자 목록에서 N 1개를 더 더하거나,빼거나, 나누거나, 곱한 수의 목록

이렇게 구할 수 있다.

 

그렇다면 목록은 어떻게 구성해야할까?

일단, count개수로 만들 수 있는 숫자들의 목록을 저장하는 딕셔너리가 필요하다.

var expressions = [Int:[Int]]()
expressions[1] = [N]   // N를 1개 사용하여 표현 가능한 숫자: N

그리고, 특정 숫자가 몇개의 N으로 표현될 수 있는지 정해지면, 그 count를 저장하는 딕셔너리가 필요하다.

var usecount = [Int:Int]()
usecount[N] = 1   // N를 표현하는 데에 필요한 숫자: 1개

 

목록을 구할 때, 유효한 숫자인지도 판단해야한다. 유효한 숫자는 다음과 같은 조건을 갖는다

• count보다 적은 개수로 만들 수 없어야 한다.
• 0보다 크고, 32000 이하인 수여야 한다.

유효한 숫자라는 판정을 내리면 목록에 추가한다!

func expressable(_ num: Int, use count: Int) {
    guard usecount[num] == nil else {return}
    guard 0 < num && num <= 32000 else {return}

    expressions[count]?.append(num)
    usecount[num] = count
}

 

1차 전체 코드

import Foundation

func solution(_ N:Int, _ number:Int) -> Int {
    
    var expressions = [Int:[Int]]()
    var usecount = [Int:Int]()
    expressions[1] = [N]   // N를 1개 사용하여 표현 가능한 숫자: N
    usecount[N] = 1   // N를 표현하는 데에 필요한 숫자: 1개
    
    func expressable(_ num: Int, use count: Int) {
        guard usecount[num] == nil else {return}
        guard 0 < num && num <= 32000 else {return}

        expressions[count]?.append(num)
        usecount[num] = count
    }
    
    for count in 2...8 {
        expressions[count] = [Int]()
        
        // N을 count번 반복
        if makeRepeating(N, count: count)==number { return count }
        expressable(makeRepeating(N, count: count), use: count)
        
        guard let last = expressions[count-1] else{ continue }
        for exp in last {
            if exp/N==number || exp-N==number || exp+N==number || exp*N==number {
                return count
            }
            expressable(exp/N, use: count)
            expressable(exp-N, use: count)
            expressable(exp+N, use: count)
            expressable(exp*N, use: count)
        }
    }
    
    return -1
}

func makeRepeating(_ num: Int, count: Int) -> Int {
    var result = 0
    for _ in 0..<count {
        result = result*10 + num
    }
    return result
}

 

하지만 위의 방법은 사칙연산 계산 상은 옳은 방식이지만, 괄호를 사용하는 경우는 고려하지 못했다.

count개를 사용한 숫자는 i개를 사용한 숫자들 & count-i개를 사용한 숫자들의 연산 결과까지 생각해야한다.

 

위의 코드를 바탕으로 다시 재구성하여 최종 코드를 완성하였다.

 

전체 코드

import Foundation

func solution(_ N:Int, _ number:Int) -> Int {
    
    if N == number {return 1}
    
    var expressions = [Int:[Int]]()
    var usecount = [Int:Int]()
    expressions[1] = [N]   // 5를 1개 사용하여 표현 가능한 숫자: 5
    usecount[N] = 1   // 5를 표현하는 데에 필요한 숫자: 1개
    
    func expressable(_ num: Int, use count: Int) {
        guard usecount[num] == nil else {return}
        guard 0 < num && num <= 32000 else {return}

        expressions[count]?.append(num)
        usecount[num] = count
    }
    
    for count in 2...8 {
        expressions[count] = [Int]()
        
        // N을 count번 반복
        if makeRepeating(N, count: count) == number { return count }
        expressable(makeRepeating(N, count: count), use: count)
        
        for i in 1..<count {
            guard let numbers1 = expressions[i], let numbers2 = expressions[count-i] else {
                continue
            }
            
            for op1 in numbers1 {
                for op2 in numbers2 {
                    if op1/op2==number||op1-op2==number||op1+op2==number||op1*op2==number {
                        return count
                    }
                    expressable(op1/op2, use: count)
                    expressable(op1-op2, use: count)
                    expressable(op1+op2, use: count)
                    expressable(op1*op2, use: count)
                }
            }
        }
    }
    return -1
}

func makeRepeating(_ num: Int, count: Int) -> Int {
    var result = 0
    for _ in 0..<count {
        result = result*10 + num
    }
    return result
}