N으로 표현

문제

프로그래머스(Programmers.co.kr) 에서 제공하는 문제입니다. 저작권 문제가 생길 수 있기 때문에 문제를 옮기지는 않겠습니다. 문제를 보고싶으신 분은 https://programmers.co.kr/learn/courses/30/lessons/42895 으로 접속하시면 됩니다.

풀이

사용하는 N 세 개를 사용해서 숫자를 만들 때를 생각해 봅시다. 이 때 숫자를 만드는 방법은 N이 두 개일때 만들어진 숫자와 N 하나를 연산하는 것입니다. N 네 개를 사용해서 숫자를 만 들면 N이 두개일 때 만들어진 숫자들은 서로 연산하거나 N이 세 개 일 때 만들어진 숫자와 N 하나를 연산하는 것입니다. 여기까지 생각하게 되면 이 문제가 전형적인 동적계획법 문제임을 알 수 있습니다.

코드

import java.util.ArrayList;
import java.util.HashSet;
class Solution {
    HashSet<Integer> check = new HashSet<Integer>();
    ArrayList<Integer>[] cache = new ArrayList[9];
    
    public int add(int left, int right) {
        return left + right;
    }
    
    public int sub(int left, int right) {
        return left - right;
    }
    
    public int mul(int left, int right) {
        return left * right;
    }
    
    public int div(int left, int right) {
        if (right == 0) return 0;
        return left / right;
    }
    
    public void addCache(int digit, int ret) {
        if (!check.contains(ret)) {
            check.add(ret);
            cache[digit].add(ret);
        }
    }
    
    public void cal(int digit, int left, int right) {
        addCache(digit, add(left, right));
        addCache(digit, sub(left, right));
        addCache(digit, mul(left, right));
        addCache(digit, div(left, right));
    }
    
    public void init(int N) {
        int temp = N;
        for (int i = 1; i < 9; i++) {
            cache[i] = new ArrayList<Integer>();
            cache[i].add(temp);
            temp *= 10;
            temp += N;
        }
    }
    
    public int solution(int N, int number) {
        
        if (N==number) {
            return 1;
        }
        
        int temp = N;
        for (int i = 1; i < 9; i++) {
            if (temp == number) return i;
            cache[i] = new ArrayList<Integer>();
            cache[i].add(temp);
            check.add(temp);
            temp *= 10;
            temp += N;
        }
        
        for (int digit = 1; digit < 9; digit++) {
            for (int i = 1; i < digit; i++) {
                int j = digit - i;
                for (int left : cache[i]) {
                    for (int right : cache[j]) {
                        cal(digit, left, right);
                        if (check.contains(number)) {
                            return digit;
                        }
                    }
                }
            }
        }
        return -1;
    }
}