[200424] 동적계획법(Dynamic Programming) - N으로 표현(level3)

1. 문제이해

- Dynamic Programming : 복잡한 문제를 "작은 문제"로 나눠서 푸는 방법. "작은 문제"들이 중복되어 풀리게 됨

   --> 주로 "재귀함수(recursive function)"을 많이 이용!!

① 하향식 알고리즘 : 문제푸는 순서는 큰 문제부터 

② 상향식 알고리즘 : 문제푸는 순서는 작은 문제부터

- number를 N으로 이루어진 사칙연산식을 이용하여 표현. N의 개수의 최솟값 구하기

 

2. 전략

- makeNumber:

N으로 만들 수 있는 모든 number들을 담은 ArrayList를 return

사칙연산 : (1개, count-1개) ... (count-1개, 1개)로 나누어 사칙연산 후 ArrayList에 담기

반복숫자 : count의 개수만큼 반복된 숫자(ex> 555)를 ArrayList에 담기

- count가 1일 때부터 makeNumber를 호출하여 number와 같다면 answer!!

 

3. 참고사항

- number가 고정된 상태에서 N으로 구성하는 것은 어려움(여기서 헤맸다ㅠㅠ)

(이유1 : +와 *는 가능한 수의 범위가 정해져있지만 -와 /는 범위제한이 없음)

(이유2 : 큰문제, 작은문제의 기준이 모호함 _ number가 크다고해서 큰 문제는 아님

ex> 55 vs 12를 5로 나타내는 문제)

 

4. 코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        int answer = 0;
        ArrayList<Integer> resultList;
        for(int i = 1; i <= 9; i++){
            if(i==9){
                answer = -1;
                break;
            }
            resultList = makeNumber(N, i);
            if(resultList.contains(number)){
                answer = i;
                break;
            }
        }
        return answer;
    }
    
    public ArrayList<Integer> makeNumber(int N, int count){
        ArrayList<Integer> resultList = new ArrayList<>();
        for(int i = 1; i < count; i++){ //count일때 가능한 모든 경우의수
            ArrayList<Integer> aList = makeNumber(N, i);
            ArrayList<Integer> bList = makeNumber(N, count-i);
            for(int a : aList){
                for(int b : bList){
                    resultList.add(a+b);
                    resultList.add(a-b);
                    resultList.add(a*b);
                    if(b != 0)  resultList.add(a/b);
                }
            }
        }
        String temp = "";
        for(int i = 0; i < count; i++){
            temp += N;
        }
        int repeatNum = Integer.parseInt(temp);
        resultList.add(repeatNum);
        return resultList;
    }
}