[JAVA/DP] 프로그래머스 N으로 표현

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/42895?language=java 

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

 

2. 풀이

• 재귀함수를 이용한 DP를 통해 풀이한다.
• 재귀함수의 매개변수로 지금까지 쓰인 숫자의 수, 현재까지의 계산 결과를 넣는다.
• for문을 통해 숫자의 갯수를 가능한 범위까지 늘려가며 +,-,/,* 연산을 한다. 최솟값이 8보다 크면 -을 return 한다.

 

3. 코드

class Solution {
    int answer = 9;
    
    public void dp(int N, int number, int count, int currentNumber){
        if(count > 8) {
            return;
        }
        if(currentNumber == number) {
            answer = Math.min(answer, count);
            return;
        }
        
        int tempNumber = 0;
        for(int i = 0; i + count < 9; i++){
            tempNumber = tempNumber * 10 + N;
            dp(N, number, count + 1 + i, currentNumber + tempNumber);
            dp(N, number, count + 1 + i, currentNumber - tempNumber);
            dp(N, number, count + 1 + i, currentNumber / tempNumber);
            dp(N, number, count + 1 + i, currentNumber * tempNumber);
        }
    }
    
    
    public int solution(int N, int number) {
        
        if(N == number) return 1;
    
        dp(N,number, 0, 0);
        
        return (answer == 9) ? -1 : answer;
    }
}