[DP] N으로 표현 - JAVA

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

프로그래머스

---

아니.. 프로그래머스 왜 푼 문제들 체크가 안되지..?

분명 풀었었는데 왜 안풀려있냐구..

그래서 또 풀었는데 또 어려웠다..

내일은 DP 다음 문제 풀어야지!!

 

아무튼 풀이 설명 해보쟈!!

 

 

이 문제에서는 살짝 특이한 부분이 있는데 바로

"최솟값이 8보다 크면 -1을 return" 이 부분이다!

요걸 아주 적극적으로 활용하면 보다 쉽게 풀 수 있다!

 

그래서 N을 1개씩 추가해서 연산한 결과를 Set에 계속 추가해준다

Set을 사용하면 중복을 제거할 수 있기 때문에 사용했다!

 

그래서 예를 들어 N이 3일 때 Set에는 [3, 33, 333, .. ] 이런 애들이 기본적으로 추가되고,

쟤네를 이용해서 사칙연산을 한 결과 또한 저장한다

 

그리고 이 과정을 모두 완료하고 마지막에 number가 Set에 존재하는지 확인한다

 

 

자바 코드)

package programmers;

import java.util.HashSet;
import java.util.Set;

public class DP1 {
    public static void main(String[] args) {
        int N = 5;
        int number = 12;
        System.out.println(solution(N, number));
    }
    public static int solution(int N, int number) {
        int answer = -1;
        int now = N;
        Set<Integer>[] setArr = new HashSet[9];
        for(int i=1;i<9;i++) {
            setArr[i] = new HashSet<>();
            setArr[i].add(now);
            now = now*10 + N;
        }

        for(int i=1;i<9;i++) {
            for(int j=1;j<i;j++) {
                for(Integer a : setArr[j]) {
                    for(Integer b : setArr[i-j]) {
                        setArr[i].add(a+b);
                        setArr[i].add(a-b);
                        setArr[i].add(b-a);
                        setArr[i].add(a*b);
                        if(a!=0) {
                            setArr[i].add(b/a);
                        }
                        if (b!=0) {
                            setArr[i].add(a/b);
                        }
                    }
                }
            }
        }

        for(int i=1;i<9;i++) {
            if(setArr[i].contains(number)) {
                answer = i;
                break;
            }
        }
        return answer;
    }
}

오케 N으로 표현 진짜 끝!!