[프로그래머스 알고리즘 고득점 Kit][동적계획법(Dynamic Programming))][Java] N으로 표현

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

 

 

처음보는 형태의 dp 문제였다.
점화식으로 이전 값을 활용하는 것이 아니라
나올 수 있는 결과들을 다음 결과들을 만드는 데 사용한다.

여기서 출력 조건이 8개보다 크면 -1을 출력을 하라고 했는데
이건 다 풀고 나서야 힌트라는 것을 알게 되었다.
8개까지만 구하고 그 이후는 계산할 필요가 없다는 생각으로

사용갯수가 1개인 것부터 하나씩 나올 수 있는 결과들을 만들어서 넘어가는  식으로 풀 수 있다.
연산의 결과가 중복이 많았기 때문에 Set으로 관리했다.

N을 1개 사용했을 때
{N}

2개 사용했을 때

{NN, N+N, N-N, N*N, N/N}  -> 이건 NN과 1개 사용한 집합의 원소들끼리 연산 한 결과를 저장한 것이다.

3개는
NNN 과 1개 사용한 집합과 2개 사용한 집합끼리 + - / * 연산을 기록해주면된다.

이렇게 나아가다가 그 집합에 가장 먼저 number가 등장한다면 그것이 최소 사용 횟수인 정답이된다.

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        if(N == number) return 1;
        
        List<Set<Integer>> dp = new ArrayList<>();
        //dp의 i번째 집합은 N을 i개 사용해서 만들 수 있는 숫자들을 저장
        //0번째 인덱스는 사용하지 않음.
        dp.add(new HashSet<>());
        
        //N을 count만큼 사용해서 나올 수 있는 숫자들을 차례로 저장할거임
        for(int count = 1; count <= 8; count++){ 
            Set<Integer> current = new HashSet<>();
            
            //N, NN, NNN, ... 
            current.add(makeRepeatedNum(N, count));
            
            //i개 사용 집합과 (count - i) 사용 집합의 원소들을 연산 = count개 사용한 집합
            for(int i=1; i<count; i++) {
                Set<Integer> left = dp.get(i); //i번 사용해서 만든 숫자들
                Set<Integer> right = dp.get(count-i);//count-i 사용해서 만든 숫자들
                 
                for(int l : left) {
                    for(int r : right) {
                        current.add(l + r);
                        current.add(l - r);
                        current.add(l * r);
                        if(r != 0) {
                            current.add(l / r);
                        }
                    }
                }
            }
            if(current.contains(number)) return count;
            
            dp.add(current);
        }
        
        //count 8보다 크면 -1 출력
        return -1;
    }
    public int makeRepeatedNum(int N, int count) {
        int num = 0;
        for(int i=0; i<count; i++) {
            num = num * 10 + N;
        }
        return num;
    }
}