[프로그래머스 고득점 kit]동적계획법 Level3 N으로 표현

문제 설명

 

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.

• number는 1 이상 32,000 이하입니다.

• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.

• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N

number

return

5	12	4
2	11	3

입출력 예 설명

 

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

접근 방법

처음 문제에 접근했을 때는 쉽게 풀릴 줄 알았다. 첫 번째 접근 방법은 다음과 같다.

 

1. 자료구조 선택

 사칙 연산을 수행하는데 중복된 원소가 있으면 불필요한 자원(시간, 공간)을 차지하기 때문에                                 Set 자료구조를 사용한다.

 

2. 연산 방법

 

먼저 반복문을 통해 N, NN, NNN ... NNNNNNNN와 같이 N이 i번 사용된 수를 만든다. 그리고 그 수를 Set에 저장한다.

 

Set에 저장된 모든 수를 N으로 사칙연산을 수행한다.

 

위와 같은 방식으로 문제를 풀어 반 정도의 테스트 케이스를 통과하였다. 논리상 오류는 없는 것 같아 반례를 찾아보기로 하였다.

 

(1) 55 * 55 = 3025 

위 알고리즘으로 수행하면 4가 아닌 6(7?)이 산출되었다. 알고리즘상 Set에 저장된 연산된 수 (사칙연산) N 밖에 수행할 수 없기 때문이다.

 

근본적인 해결책 찾기

if문을 통해 위 문제를 해결하려 했지만 근본적인 해결책이 되지 않았다.

 

문제를 다시 곰곰이 생각해보았다. 예를 들어, 어떠한 수 X가 존재할 때 X를 만들 수 있는 N의 사용 횟수는 

 

5 + 1, 3 + 2 , 4 + 2 라고 가정하였을 때 정답은 3 + 2 = 5가 되어야할 것이다. 하지만 위 알고리즘은 한번에 1씩 N의 사용 횟수가 증가하기 때문에 해결할 수 없는 것이었다.

 

 

그렇다면 N을 1번만 사용하여 만들 수 있는 경우의 수, 2번 사용하여 만들 수 있는 경우의 수, ... 8번 사용하여 만들 수 있는 경우의 수를 모두 구하여 Set에 저장하면 해결할 수 있을 것이다.

 

가령 N을 총 8번 사용하여 만들 수 있는 경우의 수는

(1, 7), (2, 6), (3, 5), (4, 4) ... (7, 1)이 될 것이다.

 

소스 코드

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        int succ = 0;
        ArrayList<Set<Integer>> setArr = new ArrayList<>();
        //Initialize
        for(int i=0;i<9;i++){
            setArr.add(new HashSet<Integer>());
        }
        
        // N, NN, NNN, NNNN ... NNNNNNNN
        for(int count=1;count<=8;count++){   
            succ += (int)Math.pow(10, count-1);
            setArr.get(count).add(succ * N);
        }
        
        for(int i=2;i<=8;i++){
            for(int j=1;j<i;j++){
                Set<Integer> set1 = setArr.get(j);
                Set<Integer> set2 = setArr.get(i - j);
               //k = i - j, k + j = i >> i를 만들 수 있는 모든 경우의 수 에 대한 사칙연산 수행
                Set<Integer> target = setArr.get(i);
                for(int el1 : set1){
                    for(int el2 : set2){
                        target.add(el1 + el2);
                        target.add(el1 - el2);
                        target.add(el1 * el2);
                        if(el2 != 0)
                            target.add(el1 / el2);
                    }
                }
            }
        }
        for(int i=1;i<setArr.size();i++){
            if(setArr.get(i).contains(number))
                return i;
        }
        return -1;
    }
}