[프로그래머스 코딩테스트] 동적계획법(Dynamic Programming) - N으로 표현

EUN JY·2022년 3월 22일
1

Coding Test

목록 보기
8/9

머리가 잘 안돌아가서 다른 사람 풀이 참고해서 풀었다...

import java.util.*;

class Solution {
    
    private int answer = -1; 
    private int N = 0;
    private int number = 0;
    
    public int solution(int NVal, int numberVal) {
        N = NVal;
        number = numberVal;
        
        calc(0, 0);
        return answer;
    }
    
    public void calc(int tempAnswer, int tempNumber) {
        if (tempAnswer > 8) {
            return; // 최솟값이 8보다 크면 -1이 return 되도록 함
        }
        
        if (number == tempNumber) {
            if (answer == -1) answer = tempAnswer;
            else answer = Math.min(answer, tempAnswer); // 가장 최소 횟수
        }
        
        int tempNN = N;
        for (int i=1; i<=(8-tempAnswer); i++) {
            calc(tempAnswer + i, tempNumber + tempNN);
            calc(tempAnswer + i, tempNumber - tempNN);
            calc(tempAnswer + i, tempNumber * tempNN);
            calc(tempAnswer + i, tempNumber / tempNN);
            tempNN = tempNN * 10 + N; // 숫자를 붙인 형태, 뒤에 올 수도 앞에 올 수도 있음
        }
        
    }
    
}
profile
개린이

0개의 댓글