[알고리즘] 프로그래머스 N으로 표현 -dfs - 자바 코틀린

programmers.co.kr/learn/courses/30/lessons/42895?language=kotlin

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

 

 

프로그래머스 N으로 표현 문제입니다. DP 유형 문제라 생각이 안나 풀이를 봤는데 DFS 로 푼 사람도 많았습니다. 저도 DFS로 풀었고 DP 로 푼 예제는 다음을 보시면 될 것 같습니다.

gurumee92.tistory.com/164

프로그래머스 문제 풀이 N으로 표현

 

풀이 방법은 주석으로 요약했습니다.

 

[Java]

class Solution {

    private static int N;
    private static int number;
    private static int answer = 9;

    static private void dfs(int count, int prev) {
        if (count > 8) {
            answer = -1;
            return;
        }
        if (number == prev && answer > count) { //답과 같고 최소의 답인 경우
            answer = count;
            return;
        }
        int n2 = N;
        for (int i = 0; i < 8 - count; i++) { // 남은 최소 개수만큼  5, 55,555... 사칙연산 경우의 수 모두 탐색
            dfs(count + i + 1, prev + n2);
            dfs(count + i + 1, prev - n2);
            dfs(count + i + 1, prev * n2);
            dfs(count + i + 1, prev / n2);
            n2 += N * (Math.pow(10, i + 1)); //5, 55, 555, 5555..
        }
    }

    public int solution(int N, int number) {
        Solution.N = N;
        Solution.number = number;
        dfs(0, 0);
        if (answer == 9) answer = -1;
        return answer;
    }
}

 

 

 

[Kotlin]

internal class Solution {
    fun solution(N: Int, number: Int): Int {
        Companion.N = N
        Companion.number = number
        dfs(0, 0)
        if (answer == 9) answer = -1
        return answer
    }

    companion object {
        private var N = 0
        private var number = 0
        private var answer = 9
        private fun dfs(count: Int, prev: Int) {
            if (count > 8) {
                answer = -1
                return
            }
            if (number == prev && answer > count) { //답과 같고 최소의 답인 경우
                answer = count
                return
            }
            var n2 = N
            for (i in 0 until 8 - count) { // 남은 최소 개수만큼  5, 55,555... 사칙연산 경우의 수 모두 탐색
                dfs(count + i + 1, prev + n2)
                dfs(count + i + 1, prev - n2)
                dfs(count + i + 1, prev * n2)
                dfs(count + i + 1, prev / n2)
                n2 += N * Math.pow(10.0, i + 1.toDouble()).toInt() //5, 55, 555, 5555..
            }
        }
    }
}