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

풀이

dp[i]는 N을 i번 사용하여 만들 수 있는 숫자들의 집합을 의미합니다.

초기값으로 dp[1]={N}를 설정합니다.

예를 들어, N=5일 때, dp[1]={5}입니다.

구체적인 점화식 설명

예제: 숫자 N=5 이고 원하는 숫자가 12인 경우

1. dp[1]: 숫자 N을 1번 사용
   • 가능한 숫자: {5}
2. dp[2]: 숫자 N을 2번 사용
   • 연속으로 붙여서 만든 숫자: {55}
   • dp[1]과 dp[1]을 사칙 연산으로 조합하여 만든 숫자:
     • {5+5, 5−5, 5∗5, 5/5}={10, 0, 25, 1}
     • 따라서 dp[2]는 {55, 10, 0, 25, 1}입니다.
3. dp[3]: 숫자 N을 3번 사용
   • 연속으로 붙여서 만든 숫자: {555}
   • dp[1]과 dp[2]를 사칙 연산으로 조합하여 만든 숫자:
     • {5+10, 5−10, 5∗10, 5/10}={15, −5, 50, 0}
   • dp[2]과 dp[1]을 사칙 연산으로 조합하여 만든 숫자:
     • {10+5, 10−5, 10∗5, 10/5}={15, 5, 50, 2}
   • 따라서 dp[3]은 {555, 15, −5, 50, 0, 5, 2}입니다.

최종 목표

이 과정을 반복하여 dp[4], dp[5]등을 구하고, 원하는 숫자 12가 등장하는 최소 dp의 인덱스를 찾는다.

• 예를 들어, dp[4]와 dp[5]를 구해보고, 이 중에서 12를 만드는 조합이 있는지 확인한다.
• 만약 dp[i]에 12가 포함되어 있다면, i가 최솟값이 된다.

N을 1개DP[1] = { 5 }

N을 2개 사용해서 수를 만드는 경우는 다음과 같다.

DP[2] = { 55, 5 + 5, 5 - 5, 5 * 5, 5 / 5 }

N을 3개 이용한다면 DP[3] = { 555, 55 + 5, 5 + 55, 5 + 5 + 5, ... } 가 될 것이다.

위의 규칙을 보면 4개 사용하는 경우도 알 수 있다. DP[4] = (DP[1] + DP[2]) + (DP[2] + DP[3]) + (DP[1] + DP[3]) + ... 이 된다는 것이다.

즉, 앞의 과정에서 사용된 수에서 사칙 연산을 진행해준 결과가 다음으로 사용된 수의 결과가 된다.

DP[1] = { N }

DP[2] = { NN } + {DP[1] 사칙연산의 조합 DP[1]}

DP[3] = { NNN } + { DP[1] 사칙연산의 조합 DP[2] } + { DP[2] 사칙연산의 조합 DP[1] }

DP[i] = DP[i - 1] + DP[i-j-1] ( 0 ≤ j ＜ i )

점화식을 찾았으니 이제 코드로 옮기면 된다!

 

fun solution(N: Int, number: Int): Int {

    // dp 배열 생성. dp[i]는 N을 i번 사용해서 만들 수 있는 모든 수의 집합.
    val dp = Array(9) { mutableSetOf<Int>() }


    // N을 i번 사용해서 만든 수를 넣어줌, 예를 들어, N=5일 때, dp[2]에는 55가 추가
    for (i in 1..8) {
        dp[i].add(N.toString().repeat(i).toInt())
    }

    // 사칙연산을 통해서 만들 수 있는 모든 경우의 수를 채움
    for (i in 1..8) {
        for (j in 1 until i) {
            for (op1 in dp[j]) {
                for (op2 in dp[i - j]) {
                    dp[i].add(op1 + op2)
                    dp[i].add(op1 - op2)
                    dp[i].add(op1 * op2)
                    if (op2 != 0) {
                        dp[i].add(op1 / op2)
                    }
                }
            }
        }
        // number를 만들 수 있다면 사용한 N의 개수를 반환
        if (dp[i].contains(number)) {
            return i
        }
    }

    // 8번까지 사용해서 만들 수 없으면 -1 반환
    return -1
}