[Programmers] N으로 표현

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

 

1. Python

def solution(N, number):
    dp = [[] for _ in range(9)]
    for i in range(1, 9):
        nums = set()
        nums.add(int(str(N)*i))
        for j in range(1, i):
            for n1 in dp[i-j]:
                for n2 in dp[j]:
                    nums.add(n1 + n2)
                    nums.add(n1 - n2)
                    nums.add(n1 * n2)
                    if n2 != 0:
                        nums.add(int(n1/n2))
        if number in nums:
            return i
        dp[i] = nums
    return -1

 

2. C++

int solution(int N, int number) {
	vector<vector<int>> dp(9, vector<int>());
	for (int i=1; i<=8; i++) {
		set<int> nums;
		stringstream ss;
		for (int t=1; t<=i; t++) {
			ss << to_string(N);
		}
		nums.insert(stoi(ss.str()));
		for (int j=1; j<i; j++) {
			for (int n1 : dp[i-j]) {
				for (int n2: dp[j]) {
					nums.insert(n1 + n2);
					nums.insert(n1 - n2);
					nums.insert(n1 * n2);
					if (n2 != 0) {
						nums.insert(int(n1/n2));
					}
				}
			}
		}
		if (nums.find(number) != nums.end()) {
			return i;
		}
		vector<int> tmp;
		tmp.assign(nums.begin(), nums.end());
		dp[i] = tmp;
	}
	return -1;
}

 

3. Java

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        List<List<Integer>> dp = new ArrayList<>();
        dp.add(new ArrayList<>());
        for(int i=1; i<=8; i++) {
            Set<Integer> nums = new HashSet<>();
            nums.add(Integer.valueOf(String.valueOf(N).repeat(i)));
            for (int j=1; j<i; j++) {
                for (int n1 : dp.get(i-j)) {
                    for (int n2 : dp.get(j)) {
                        nums.add(n1 + n2);
                        nums.add(n1 - n2);
                        nums.add(n1 * n2);
                        if (n2 != 0) {
                            nums.add(n1/n2);
                        }
                    }
                }
            }
            if (nums.contains(number)) return i;
            List<Integer> tmp = new ArrayList<>(nums);
            dp.add(tmp);
        }
        return -1;
    }
}