프로그래머스[programmers] - N으로 표현(Kotlin)[LV2]

문제

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

프로그래머스

 

문제 풀이

처음 볼 때 DP 문제라고 생각을 하지 못했는데, 손으로 써 내려가면서 DP문제라는 것을 깨달았다.

우선 우리는 목표 숫자를 N이라는 숫자를 여러번 사용해서 표현해야 한다.

여기서 왜 DP이냐에 대해서 생각을 해보자.

 

만약 5를 3번 쓸 경우 만들수 있는 숫자의 조합은 무엇일까?

이걸 구하기 위해서는 5를 1번 쓸 경우, 5를 2번 쓸 경우에 대해서 구해야 한다. 

이유는 써 내려가면 알 수 있다.

5를 1번 쓰는 경우 : 5 

5를 2번 쓰는경우 : 55,10(5+5), 0(5-5), 25(5*5),1(5/5)

5를 3번 쓰는경우 : 555, 15(10+5),50(10*5),5(10-5),2(10/5), 30(25+5),20(25-5),125(25*5),5(25/5),

6(1+5),-4(1-5),5(1*5), 60(55+5), 50(55-5), 225(55*5), 11(55/5)

 

규칙이 보일것입니다. 즉 이전에 썼던 숫자들을 다음 연산에서 활용하는 것입니다.

따라서 해당 문제는 DP 알고리즘을 사용하는 것입니다.

 

즉 DP [i]의 결과는 DP [j]의 결과 & DP [j-i]의 결과를 조합해서 만들 수 있는 숫자들의 합입니다.

정리하자면

DP [i]는 N을 i번 사용해서 얻을 수 있는 숫자들의 집합입니다.

저는 DP의 자료형을 Int값과 Set을 가지는 class를 넣어줬습니다.

사실 Map이랑 똑같은 의미입니다ㅎ.

 

최종적으로 DP [i]에는 DP [i-j], DP [j] 두 숫자의 조합들에 사칙연산을 한 결과와 , N을 i번 나열한 수가 저장됩니다.

그러다가 DP [i]를 구하고, 만약 i에 목표 숫자가 있다면 그때 i를 반환합니다.

이때 i는 목표 숫자를 만들 때 사용되는 N의 등장 횟수가 됩니다.

만약 만들지 못한다면 -1을 리턴해줍니다.

 

전체 코드

import java.util.*
class Solution {
    var answer = 0

    var dp = mutableListOf<num>()
    fun solution(N: Int, number: Int): Int {
        if(N==number)
            return 1
        getNum(N,number)
        return answer
    }
    fun getNum(N : Int, number : Int){
        var temp=1
        dp.add(num(0))
        for(i in 1 .. 8){
            dp.add(num(i))
            if(dp.size==2)  {
                dp[dp.size-1].setList.add(N)
            }
            else dp[dp.size-1].setList.add(dp[dp.size-2].findFirst()*10+N)
        }
        answer = calculate(N,number)
    }
    fun calculate(N:Int,number:Int) : Int{ 

        for(i in 1 until dp.size){ 
            for(j in 1 .. i){
                for(first in dp[j].setList){
                    for(second in dp[i-j].setList){
                        dp[i].addNum(first,second)
                    }
                }
                if(dp[i].findNum(number))
                    return i
            }
        }
        return -1
    }

    data class num(val id : Int){
        var setList = HashSet<Int>()

        fun addNum(first:Int, second:Int){
            setList.add(first+second)
            setList.add(first-second)
            setList.add(first*second)
            if(second!=0)
                setList.add(first/second)
        }
        fun findFirst() : Int {
            return setList.first()
        }
        fun findNum(n:Int) : Boolean{
            return setList.contains(n)
        }
    }
}