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

코딩테스트 연습 > 동적계획법(DP)

---

N으로 표현

---

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

코딩테스트 연습 - N으로 표현

 

DP 문제이다. 원래는 DFS로도 풀릴 것 같아 시도해보았으나, 아마 테스트케이스 추가 이전까지는 완전탐색으로도 풀리는 문제인듯 했으나, 그 방식으로는 추가된 테스트케이스를 통과하지 못했다.

 

이 문제의 착안점

N을 총 8개까지 사용할 수 있는데, N을 M개 써서 나오는 경우의 수 + N을 (8-M)개 써서 나오는 경우의 수를 사칙연산하여 나오는 결과이다.

 

이 부분에 착안하여, N을 M개 써서 나오는 경우의 수를 hashSet에 넣은 뒤 차례차례 조합하며 사칙연산을 진행하면 됩니다.

 

import java.util.*;

class Solution {
    static int origin;
    HashSet<Integer>[] sets;

    public int solution(int N, int number) {
        int answer = 0;
        origin = N;
        sets = new HashSet[9];
        for(int i=1; i<=8; i++) {
            getNum(i);
            if(sets[i].contains(number)){
                return i;
            }
        }
        
        return -1;
    }
    
    public HashSet<Integer> getNum(int n) {
        if(sets[n]!=null){
            return sets[n];
        }
            
        int num = 0;
        for(int i=0; i<n ; i++){
            num = 10 * num + origin;
        }
        
        sets[n] = new HashSet<>();
        sets[n].add(num);
        
        for(int i=1; i<n; i++) {
            int j = n-i;
            if(sets[i]!=null || sets[j]!=null){
                getNum(i);
                getNum(j);
            }
            for(int n1 : sets[i]) {
                for(int n2 : sets[j]) {
                    sets[n].add(n1+n2);
                    sets[n].add(n1-n2);
                    sets[n].add(n1*n2);
                    if(n2!=0) {
                        sets[n].add(n1/n2);
                    }
                }
            }
        }
        return sets[n];
    }
}