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

요구능력

DP

 

문제풀이

이 문제는 N을 이용해서 number를 만드는데 N을 최소개수로 사용해서 number를 만들때 몇개를 써야하는지를 묻는문제이다.

 

DP를 생각하게된 이유?

카테고리가 DP로 분류되어있다.

예제를 보자.

12 = (55 + 5)/5 가 있다.

이게 5를 4번 사용한것이라고한다.

그렇다면 55는 5를 2번사용했다는 말이되는데,

(55 + 5)는 5를 3번 사용한것이다.

DP문제를 조금 풀어봤으면 감이 올것이다.

현재 이 식은 dp[4] = dp[3] + dp[1]과 같은 형태구나 라는것을..

사실, dp는 다른 알고리즘 문제들과는 조금다르게 감각(?)이 필요한 문제같다.

그래서 다양한문제를 많이 접해봐야하는데,

만약 이런감이 안잡힌다면, DP문제를 많이 풀어보기를 추천드립니다.

 

이 문제는 일반적인 DP처럼 갯수만 저장하는것이 아닌, number라는 수를 표현할 수 있는지를 알아야된다.

그래서 우리는 DP에 연산되는 수들을 다 저장할것이다.

그냥 배열에 저장하면 안된다.

dp[3] = dp[2] + dp[1]의 경우에는 dp[1] + dp[2]와 같은 경우가 나올 수 있다.

그래서 Set자료형을 사용한다.

 

아니, 그럼 dp[2] + dp[1]만하고 dp[1] + dp[2]는 안하면 되잖아요?

할수도 있는데, dp[2] - dp[1]과 dp[1] - dp[2]의 경우나

dp[2] / dp[1] 과 dp[1]/dp[2]의 경우에는 다른결과가 나오게된다.

그래서 3 = 3,

1 + 2,

2 + 1

의 경우를 모두 확인해야한다.

 

그리고 아까 예제에서 55와 같은 자신을 연속으로 여러번사용하는 경우도 따로추가를 해줘야하는데,

나는 문자열을 합쳐서 추가해줬다.

 

후기

DP에 수만 저장하는것이 아닌 DP문제

코드

func solution(_ N:Int, _ number:Int) -> Int {
    var dp = Array(repeating: Set<Int>(), count: 9)
    var result = Int.max
    for i in 1..<9{
        for j in 1..<i{
            for k in dp[i - j]{
                for l in dp[j]{
                    
                    if k - l > 0{
                        dp[i].insert(k - l)
                        if k - l == number{result = min(result, i)}
                    }
                    if l != 0 && k != 0{ //Division by zero 처리
                        dp[i].insert(k / l)
                        if k / l == number{result = min(result, i)}
                    }
                    dp[i].insert(k + l)
                    dp[i].insert(k * l)
                    if k + l == number{result = min(result, i)}
                    if k * l == number{result = min(result, i)}
                }
            }
        }
        var str = ""
        for _ in 1...i{
            str += "\(N)"
        }
        dp[i].insert(Int(str)!)
        if Int(str)! == number{result = min(result, i)}
    }
    if result == Int.max{
        result = -1
    }
    return result
}