Programmers - N으로 표현 with JAVA (V)

 

문제

주어진 N이라는 숫자와 사칙연산을 가지고 number라는 숫자를 만들 떄, N이라는 숫자를 최소한으로 사용해 만들고자 한다. 이 떄, 최소한의 개수를 구하라.

 

 

 

 

로직 ( DP : i개의 N으로 만들 수 있는 수)

1. 우선적으로, 만약 N==number라면 숫자 1개로 number를 만들 수 있으므로 1을 return 한다.

2. 문제에서 주어진 N을 사용할 수 있는 횟수는 최대 8회이다. 따라서 1회부터 8회까지 만들 수 있는 리스트를 담을 dp를 선언한다.

(Set을 사용하여 중복을 허용하지 않는다.)

3. 초기값으로 그냥 HashSet을 넣는다. (인덱스 0을 위함.)

4. 1개로 만들 수 있는 수는 N밖에 없으므로 그대로 넣는다.

5. 이 후 2개를 사용하여 만들 수 있는 수부터 8개를 사용하여 만들 수 있는 수들을 dp에 순차적으로 넣는다.

5-1. 넣을 때, 만약 N=5라면 2개를 사용하면 55, 3개를 사용하면 555도 만들 수 있으므로 넣는다.

5-2. 사칙 연산을 하는데 아래의 논리 설명을 참고하여 로직을 구성해 셋에 넣는다.

5-3 number를 만들기 위한 최소한의 경우를 구하므로 만약 지금 사용하고 있는 N의 수가 number와 같다면 종료 가능하다.

(따라서, 최선의 경우 굳이 8까지 모두 계산하지는 않는다.)

 

 

논리 설명

만약 N=5라고 가정하자.

이 때, 2개를 사용하면 5/5, 5*5, 5+5, 5-5를 만들 수 있다.

이 때, 3개를 사용하면 5 + 2개를 사용한 경우, 5 - 2개를 사용한 경우, 5 * 2개를 사용한 경우 처럼 이어 나갈 수 있으며, 반대의 경우도 포함한다. 예를 들어, 2개를 사용한 경우 + 5 같은 경우를 의미한다.

이 후, 최대 8개를 사용한 경우까지 만들 수 있는 수를 구한다.

 

 

코드

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        if(N == number){
            return 1;
        }
        List<HashSet<Integer>> check = new ArrayList<>();
        check.add(new HashSet<>());
        HashSet<Integer> start = new HashSet<>();
        start.add(N);
        check.add(start);
        for(int i=2; i<=8; i++){
            HashSet<Integer> now = new HashSet<>();
            int value = 0;
            for(int j=0; j<i; j++){
                value += Math.pow(10, j)*N;
            }
            if(value == number){
                return i;
            }
            now.add(value);
            for(int j=1; j<i; j++){
                HashSet<Integer> values1 = check.get(j);
                HashSet<Integer> values2 = check.get(i-j);
                for(int value1 : values1){
                    for(int value2 : values2){
                        if(value1 * value2 == number){
                            return i;
                        }
                        now.add(value1 * value2);
                        if(value1 - value2 == number){
                            return i;
                        }
                        if(value1 - value2 >= 0){
                            now.add(value1 - value2);   
                        }
                        if(value2 != 0){
                            if(value1 / value2 == number){
                                return i;
                            }
                            now.add(value1 / value2);   
                        }
                        if(value1 + value2 == number){
                            return i;
                        }
                        now.add(value1 + value2);
                    }
                }
            }
            check.add(now);
        }
        return -1;
    }
}