* [파이썬] [DP] Pro N으로 표현

문제

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

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

 

코드

def solution(N, number):
    array=[None]+[{int(str(N)*i)} for i in range(1,9)]
    for i in range(1,9):
        for j in range(1,i):
            for num1 in array[j]:
                for num2 in array[i-j]:
                    array[i].add(num1+num2)
                    array[i].add(num1*num2)
                    array[i].add(num1-num2)
                    if num2:
                        array[i].add(num1//num2)
        if number in array[i]:
            return i
    return -1

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        if(N==number){
            return 1;
        }
        ArrayList<Set<Integer>> dp = new ArrayList<>();
        Set<Integer> sub = new HashSet<>();
        
        // dp[0]을 null로 채우기 위해
        sub.add(0);
        dp.add(sub);
        
        // dp[1]="5", dp[2]="55", dp[3]="555" 초기화
        for (int i=1; i<=8; i++){
            Set<Integer> sublist = new HashSet<>();
            String value = "";

            for (int j = 1; j <= i; j++) {
                value += String.valueOf(N);
            }

            sublist.add(Integer.valueOf(value));
            dp.add(sublist);
        }
        
        // i가 4인 경우
        // dp[1],dp[3] 배열에 있는 값끼리 사칙연산
        // dp[2],dp[2] 배열에 있는 값끼리 사칙연산
        for (int i=2; i<=8; i++){
            for (int j=1; j<=i-1; j++){
                for(Integer k :dp.get(j)){
                    for (Integer l :dp.get(i-j)){
                        dp.get(i).add(k+l);
                        dp.get(i).add(k-l);
                        dp.get(i).add(k*l);
                        if (l!=0){
                            dp.get(i).add(k/l);
                        }
                    }
                }
            }
            // 최종값 number가 포함되어 있으면 index 리턴
            if (dp.get(i).contains(number)){
                return i;
            }
        }
        
        return -1;
    }
}

생각 정리

만약, N=5일때

arr[1] => 5

arr[2] => 55 , 5+5, 5-5, 5*5, 5//5

이런식으로 전개된다

5를 4번 사용한 경우(arr[4])를 생각해보면,

arr[1] (+ - * //) arr[3]

arr[2] (+ - * //) arr[2]

arr[3] (+ - * //) arr[1]

에서 중복을 제거한 수들이 될것이다.