N으로 표현 kotlin

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

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

 

 

문제 설명

아래와 같이 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으로 주어진 수를 표현하는 문제이다.

해결방법 : 8개를 써서 만들 수 있는 모든 경우의 수를 구한 뒤, 가작 적게 사용한 경우의 수를 구한다.

N으로 특정 수를 만드는 방식을 정리하면 아래와 같다.

* N은 5라고 가정한다.

N 1 : 5
N 2 : 55, 5+5(10), 5*5(25), 5 / 5(1), 5-5(0)

N 3 : 555, 55+5(60), 55*5(275), 55/5(11), 55-5(50)

....

사칙연산의 결과 + 숫자 이어붙이기(NN, NNN)

위와 같은 규칙을 통해 숫자들을 만들 수 있다. 즉, 위의 조합에서 나오는 숫자들의 조합에서만 숫자가 나온다.

import kotlin.math.min

class Solution {


    // target은 최대 8이기에 초기 값은 9로 설정 . 
    var result = 9
    var target = 0

    fun solution(N: Int, number: Int): Int {
        var answer = 0

        target = number
        logic(N,0,0)

        if (result == 9) {
            return -1
        }
        return result

    }

    n: 사용해야 하는 숫자, cnt: n을 사용한 횟수, 계산 결과
    fun logic(n: Int, cnt: Int, current: Int){
        if(cnt > 8){
            return
        }

        if(current == target){
            result = min(result,cnt)
            return
        }

        var nextNum = n
        // cnt가 8을 넘지 않도록 한다. 
        for (i in 0 until 8 - cnt) {
            logic(n, cnt+1 + i, current + nextNum)
            logic(n, cnt+1 + i, current - nextNum)
            logic(n, cnt+1 + i, current * nextNum)
            logic(n, cnt+1 + i, current / nextNum)
            nextNum += n * Math.pow(10.0, i + 1.toDouble()).toInt()
        }

    }
}

1. N을 통해 숫자들을 만든다.
2. 1의 결과가 답이 아니라면, 해당 숫자의 사칙 연산을 통해 current를 수정한다.
3. 2의 결과가 답이 아니라면, 그 숫자들을 수식에 포함하여 다시 사칙연산을 수행한다.
4. 숫자를 이어붙여 2의 과정을 반복한다.
5. 답이 나온다면 cnt가 적은 쪽을 답으로한다.