프로그래머스 N으로 표현

이 문제는 동적 프로그래밍(Dynamic Programming)을 통해 해결할 수 있다.

동적 프로그래밍이란 한번 해결했던 문제를 메모리에 저장해 다음번 계산에 다시 활용하여 문제를 해결하는 방법이다. 프로그래밍에 있어 이미 계산했던 값을 다시 계산하는 것은 굉장히 비효율적이므로 평소에도 동적 프로그래밍을 적용할 수 있게 노력하는게 중요하다고 생각한다.


동적 프로그래밍을 활용해 문제를 풀 수 있는 조건은 다음과 같다.

  1. 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때


  1. 중복되는 부분 문제(Overlapping Subproblem)- 동일한 작은 문제를 반복적으로 해결해야 할 때

(재귀 함수의 시간복잡도를 줄일 수 있음)


EX

피보나치 수열의 경우 이전에 계산했던 값을 이용해 다음 값을 계산 가능 (1번 조건 만족)


재귀함수로 구현한다면 중복되는 계산에 의해 비효율적인 시간복잡도를 갖는다 (2번 조건 만족)


점화식

An = An-1 + An-2


일반적인 경우 탑다운(하향식) 보다는 바텀업(상향식) 방식을 많이 사용되며 이전 값을 저장해놓은 배열이나 리스트를 DP테이블 이라고 한다.


풀이

풀이 1


class Solution {
    fun solution(N: Int, number: Int): Int {
        var answer = 0
        sol.target = number
        sol.N = N
        sol.dfs(0,0) // prev, count
        return if(sol.answer>8) -1 else sol.answer
    }
    
    object sol{
        var target = 0 // target
        var answer = 9
        var N = 0 // N
        
        fun dfs(prev: Int, count: Int){
            if(count > 8) return
            else if(prev == target && count < answer){
                answer = count
                return
            }
            
            var p = N
            for(i in 0 until 8-count){
                if(p!= 0){
                    dfs(prev+p, count+i+1)
                    dfs(prev-p, count+i+1)
                    dfs(prev*p, count+i+1)
                    dfs(prev/p, count+i+1)
                }
                p = p*10 + N
            }
            
        }
    }
}