[JAVA] 프로그래머스: N으로 표현

# 문제 내용

프로그래머스: N으로 표현

프로그래머스

 

# 알고리즘 분류

• 다이나믹 프로그래밍

 

# 풀이

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        List<Set<Integer>> countList = new ArrayList<>();
        
        // dp 테이블 초기화
        // dp는 n을 8개까지 조합하여 만들 수 있는 집합의 리스트
        // 최소 가능한 값은 8까지이므로 8까지만 만듦
        for (int i = 0; i < 9; i++) {
            countList.add(new HashSet<>());
        }
        
        // N 1개로 만들수 있는 값은 오로지 N 하나 뿐이므로
        countList.get(1).add(N);
        
        // N 2개부터 9개까지 만들 수 있는 값을 집합에 담기
        // 동일한 결과값은 중복을 제거해야하므로 집합 사용
        for (int i = 2; i < 9; i++) {
            Set<Integer> countSet = countList.get(i);
            
            // 현재 주어진 개수의 이전 개수에서부터 차례로 +N, -N, /N, *N, NN 조합을 만들어 담기
            // (ex) i = 4일 경우, 1개 + 3개 조합, 2개 + 2개 조합, 3개 + 1개 조합, 4개 단독 조합
            
            // 사칙 연산으로 가능한 값 계산
            for (int j = 1; j <= i; j++) {
                Set<Integer> preSet = countList.get(j);
                Set<Integer> postSet = countList.get(i-j);
                
                for (int preNum : preSet) {
                    for (int postNum : postSet) {
                        countSet.add(preNum + postNum);
                        countSet.add(preNum - postNum);
                        countSet.add(preNum * postNum);
                        
                        if (preNum != 0 && postNum != 0) {
                            countSet.add(preNum / postNum);
                        }

                    }
                }
            }
            
            // 반복값 추가
            countSet.add(Integer.parseInt(String.valueOf(N).repeat(i)));
        }
        
        
        // 가능한 최소값 리턴
        // 1개로 만들 수 있는 값부터 시작해 순차적으로 확인해 해당 값이 존재할 경우 바로 리턴
        for (Set<Integer> list : countList) {
            if (list.contains(number)) {
                return countList.indexOf(list);
            }
        }
        
        // 최소값 8번으로 만들 수 없는 경우
        return -1;
    }
}

 

# References

https://born2bedeveloper.tistory.com/38

[프로그래머스] N으로 표현-JAVA