프로그래머스 - N으로 표현(Java)

DP 문제입니다.

 

1~9까지의 숫자 N이 주어졌을 때, 해당 숫자를 8개 미만으로만 사용하여 number의 값을 구하는 문제입니다.

우선 덧셈 공식을 먼저 생각을 해야하는 문제입니다.

그림과 같이 2 이상의 수는 두 자리의 덧셈으로 나타낼 수 있습니다.

이것을 단순히 덧셈이 아니라 경우의 수로 바꿔서 생각해야 합니다.

 

N이 4가 주어진다고 가정하겠습니다.

주어진 4를

1개 사용하면 {4}입니다.

2개 사용하면 {44, 4+4, 4-4, 4*4, 4/4}  = {44, 8, 0, 16, 1}입니다.

    즉, 1개를 사용한 것에서 사칙연산 및 이어 붙이기를 한 것이 됩니다.

3개를 사용하면 {444, 4+4+4, 4+4-4, (4+4)*4, (4+4)/4, 4-4+4, 4-4-4, ...}입니다.

    즉, 2개를 사용한 것과 4와 사칙 연산 및 이어 붙이기를 한 것이 됩니다.

그림과 같이 4를 4개를 사용하여 표현하는 방법은 {4444}뿐 입니다.

4를 

1개로 표현하는 경우와 3개로 표현하는 경우

2개로 표현하는 경우와 2개로 표현하는 경우

3개로 표현하는 경우와 1개로 표현하는 경우가 나옵니다.

 

당부 드리지만, 위 그림에서 '+'는 덧셈이 아닙니다.

경우의 수 이기 때문에 합집합 'U'으로 생각하셔야 합니다.

 

추가로 i=4이고, '+'기호 좌측이 j라고 하면 우측은 i-j가 됩니다.

 

[구현 코드]

import java.util.*;

class Solution {
    private static List<Set<Integer>> totalList;

    public static int solution(int N, int number) {

        totalList = new ArrayList<>();
        for(int i=0; i<9; i++){
            totalList.add(new HashSet<>());
        }

        totalList.get(1).add(N);
        for(int i=2; i<9; i++){
            Set<Integer> tmp = totalList.get(i);

            for(int j=1; j<i+1; j++){
                // 좌측
                Set<Integer> preSet = totalList.get(j);
                // 우측
                Set<Integer> postSet = totalList.get(i-j);

                for (int pre : preSet) {
                    for (int post : postSet) {
                        tmp.add(pre + post);
                        tmp.add(pre - post);
                        tmp.add(pre * post);

                        if(pre!=0 && post!=0){
                            tmp.add(pre/post);
                        }
                    }
                }

                // 숫자 반복
                // 예를 들어, 4를 두 번 반복하면 {44}임
                StringBuilder sb = new StringBuilder();
                for(int k=0; k<i; k++){
                    sb.append(N);
                }
                tmp.add(Integer.parseInt(sb.toString()));
            }
        }

        // 작은쪽 부터 확인하여 값을 찾음
        for (Set<Integer> sets : totalList) {
            if(sets.contains(number)){
                return totalList.indexOf(sets);
            }
        }

        return -1;
    }
}